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],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; }
