CF传送门
洛谷传送门
解题思路
题目中有几个需要注意的翻译得不是很好的点：
- 无根树
- 最后还需要输出每次选取和删除的点
我们回顾一下树的直径dfs求法，可知树上到任意一个点距离最远的点一定是树的直径的一个端点。所以我们可以选取树的直径的某个端点作为整棵树的根，然后对于每个叶子节点：
- 若不在直径上，比较一下到两个直径端点哪个更远，取更远的那个
- 若是直径上的点，为了保护直径，我们先不处理，最后单独处理直径（一条链，对答案的总贡献为l*(l+1)/2，l为直径长度）
注意最后输出的时候一定要按照顺序（从叶子节点出发）。
AC代码
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstdio> 5 #include<cstring> 6 using namespace std; 7 const int maxn=200005; 8 int p[maxn],dis[maxn],dep[maxn],fa[maxn],vis[maxn],anss[maxn]; 9 int n,cnt,maxd,rt1,rt2; 10 long long ans,l; 11 struct node{ 12 int v,next; 13 }e[maxn*2]; 14 void insert(int u,int v){ 15 cnt++; 16 e[cnt].v=v; 17 e[cnt].next=p[u]; 18 p[u]=cnt; 19 } 20 void dfs(int u,int f){ 21 for(int i=p[u];i!=-1;i=e[i].next){ 22 if(e[i].v==f) continue; 23 fa[e[i].v]=u; 24 dep[e[i].v]=dep[u]+1; 25 if(dep[e[i].v]>dep[maxd]) maxd=e[i].v; 26 dfs(e[i].v,u); 27 } 28 } 29 void dfs2(int u,int f){ 30 for(int i=p[u];i!=-1;i=e[i].next){ 31 if(e[i].v==f) continue; 32 dis[e[i].v]=dis[u]+1; 33 dfs2(e[i].v,u); 34 } 35 } 36 void dfs3(int u,int f){ 37 for(int i=p[u];i!=-1;i=e[i].next){ 38 if(e[i].v==f) continue; 39 dfs3(e[i].v,u); 40 } 41 if(!vis[u]) printf("%d %d %d ",u,anss[u],u); 42 } 43 int main() 44 { 45 memset(p,-1,sizeof(p)); 46 scanf("%d",&n); 47 for(int i=1;i<n;i++){ 48 int u,v; 49 scanf("%d%d",&u,&v); 50 insert(u,v); 51 insert(v,u); 52 } 53 dfs(1,-1); 54 dep[maxd]=0; 55 rt1=maxd; 56 fa[maxd]=-1; 57 dfs(maxd,-1); 58 rt2=maxd; 59 l=dep[rt2]; 60 for(int i=rt2;i!=-1;i=fa[i]) vis[i]=1; 61 dfs2(rt2,-1); 62 for(int i=1;i<=n;i++){ 63 if(vis[i]==0){ 64 if(dep[i]>dis[i]){ 65 anss[i]=rt1; 66 ans+=dep[i]; 67 }else{ 68 anss[i]=rt2; 69 ans+=dis[i]; 70 } 71 } 72 } 73 ans+=(l+1)*l/2; 74 printf("%lld ",ans); 75 dfs3(rt1,-1); 76 for(int i=rt2;i!=rt1;i=fa[i]) printf("%d %d %d ",i,rt1,i); 77 return 0; 78 }