视频链接：
CF911F Tree Destruction - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// 两次DFS + 贪心 O(n) #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std;const int N=200005; int head[N],idx; struct edge{int to,ne; }e[N<<1]; void add(int x,int y){e[++idx]={y,head[x]};head[x]=idx; } int n,p,l,r,d[N],fa[N],on[N]; long long ans; vector<pair<int,int>>s;void dfs(int x,int f){fa[x]=f;if(d[x]>d[p]) p=x;for(int i=head[x];i;i=e[i].ne){int y=e[i].to;if(y==f) continue;d[y]=d[x]+1;dfs(y,x);} } void work(int x,int rt){for(int i=head[x];i;i=e[i].ne){int y=e[i].to;if(d[y]>d[x]) work(y,on[y]?y:rt);//若y在直径上,则取y//若y不在直径上,则取直径上的节点 }if(!on[x]){ //若x不在直径上if(d[x]>d[x]+d[r]-d[rt]*2){ans+=d[x];s.push_back({l,x});}else{ans+=d[x]+d[r]-d[rt]*2;s.push_back({r,x});}} } int main(){scanf("%d",&n);for(int i=1,x,y;i<n;++i){scanf("%d%d",&x,&y);add(x,y); add(y,x);}dfs(1,0); l=p; d[p]=0;dfs(p,0); r=p;for(int i=r;i;i=fa[i]) on[i]=1;work(l,l); //删外周for(;l!=r;r=fa[r]) //删直径ans+=d[r],s.push_back({l,r});printf("%lld\n",ans);for(auto i:s)printf("%d %d %d\n",i.first,i.second,i.second); }
