题目链接
思路：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。 那么题目所求的就是每颗子树的重心了。 dfs的时候求出每个子树的重心和最短距离，考虑怎么合并所有子树。 这时候要用到第二个性质了：把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。 那么这样就相当于重心在往上爬，我们可以让重心一直跳，找到根在这个子树上时，最短的距离和。 对所有子树处理一遍就能找到最小距离和所有的重心了。 转移的时候自己推一推贡献即可。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int n,f[N],sz[N],dep[N]; LL sum[N],need[N]; vector<int>v[N]; vector<int>ans[N]; void dfs(int x,int y,int de=0){ f[x]=y; dep[x]=de; sum[x]=de; sz[x]=1; ans[x].pb(x); for(auto k:v[x])if(k!=y){ dfs(k,x,de+1); sz[x]+=sz[k]; sum[x]+=sum[k]; } LL co=sum[x]-1ll*de*sz[x]; int ro=x; for(auto k:v[x])if(k!=y){ int res=ans[k][0]; LL ne=need[k]; vector<int>tmp; tmp.pb(res); ne+=sum[x]-sum[k]-1ll*(sz[x]-sz[k])*dep[x]; ne+=1ll*(dep[res]-dep[x])*(sz[x]-sz[k]); while(f[res]!=x){ int fa=f[res]; LL re=ne-(sz[x]-sz[k]); re+=sz[res]; re-=(sz[k]-sz[res]); if(re<ne){ tmp.clear(); ne=re; res=fa; tmp.pb(res); }else if(re==ne){ tmp.pb(fa); res=fa; }else break; } if(ne<co){ co=ne; ans[x]=tmp; }else if(ne==co){ for(auto k:tmp)ans[x].pb(k); } } need[x]=co; } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<n;i++){ int s,t; cin>>s>>t; v[s].pb(t); v[t].pb(s); } dfs(1,0); for(int i=1;i<=n;i++){ int sz=ans[i].size(); sort(ans[i].begin(),ans[i].end()); for(int j=0;j<sz;j++){ cout<<ans[i][j]<<" \n"[j==sz-1]; } } return 0; }