CF911F5
This is my code. Help me please! I know people in Codeforces are helpful people.
include
include
include
include
include
include
include
include
include
include
define int long long
using namespace std;
const int maxn=200010;
int n,head[maxn],cnt,qidian=1,zhongdian=1,dis[maxn][3];
int zhijingshangdedian[maxn],ans,zhijing[maxn],du[maxn],fa[maxn],len,root=1,chudu[maxn];
struct edge
{
int to,next;
}e[maxn<<1];
queueq;
inline int read()
{
int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1;
ch=getchar();
} while(ch>='0'&&ch<='9') {
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
} return x*f;
}
inline void write(int a)
{
if(a<0) {
char a='-',b='1';
putchar(a);
putchar(b);
} else {
if(a>=10)
write(a/10);
putchar(a%10+'0');
}
}
void add(int from,int to)
{
e[++cnt]=(edge){to,head[from]}; head[from]=cnt;
}
void dfs(int now,int father,int cishu)
{
if(!cishu)
fa[now]=father;
for(int i=head[now];i;i=e[i].next) {
int to=e[i].to;
if(to==father)
continue;
if(!cishu)
chudu[now]++;
dis[to][cishu]=dis[now][cishu]+1;
dfs(to,now,cishu);
}
}
int xunzhaozhijing(int now,int father)
{
if(now==zhongdian) {
zhijingshangdedian[now]=1;
zhijing[1]=now;
return 1;
} for(int i=head[now];i;i=e[i].next) {
int to=e[i].to;
if(to==father)
continue;
int check=xunzhaozhijing(to,now);
if(check)
{
zhijingshangdedian[now]=1; zhijing[check+1]=now; return check+1;
}
} return 0;
}
signed main()
{
n=read(); for(int i=1;i<n;i++) {
int u=read(),v=read();
add(u,v),add(v,u);
du[u]++,du[v]++;
} for(int i=1;i<=n;i++)
if(du[i]>1)
{
root=i; break;
}
dfs(root,0,0); for(int i=1;i<=n;i++)
if(dis[i][0]>dis[qidian][0])
qidian=i; dfs(qidian,0,1); for(int i=1;i<=n;i++)
if(dis[i][1]>dis[zhongdian][1])
zhongdian=i; dfs(zhongdian,0,2); xunzhaozhijing(qidian,0); for(int i=1;i<=n;i++)
if(!zhijingshangdedian[i])
ans+=max(dis[i][1],dis[i][2]); len=dis[qidian][2]+1;
// write(len),puts("");
ans+=len*(len-1)/2; write(ans),puts(""); for(int i=1;i<=n;i++)
if(!chudu[i]&&!zhijingshangdedian[i])
q.push(i); zhijingshangdedian[0]=1; while(!q.empty()) {
int now=q.front();
q.pop();
write(now),putchar(' ');
if(dis[now][1]>dis[now][2])
write(qidian),putchar(' '),write(now);
else
write(zhongdian),putchar(' '),write(now);
puts("");
chudu[fa[now]]--;
if(!chudu[fa[now]]&&!zhijingshangdedian[fa[now]])
q.push(fa[now]); } for(int i=1;i<len;i++)
write(qidian),putchar(' '),write(zhijing[i]),putchar(' '),write(zhijing[i]),puts("");
return 0;
}