题意很简单,类似于找树的重心,代码如下.
#include<bits/stdc++.h> using namespace std; #define ll long long #define MAXN 200005 #define rep(n) for(int i=1;i<=n;i++) #define rall(x) for(int i=(x).size()-1;i>=0;i--) #define all(x) for(int i=0;i<(x).size();i++) int size[MAXN]; int son[MAXN]; vector<int>e[MAXN]; int ans[MAXN]; int pre[MAXN]; void dfs(int rt,int fa) { size[rt]=1; for(auto it:e[rt]) { if(it!=fa) { pre[it]=rt; dfs(it,rt); size[rt]+=size[it]; if(size[it]>size[son[rt]]) son[rt]=it; } } if (size[son[rt]] < size[rt] - size[son[rt]]) ans[rt]=rt; else if(size[son[rt]]==size[rt] - size[son[rt]]) ans[rt]=son[rt]; else { int now=ans[son[rt]]; while(size[now]<(size[rt]+1)/2) { now=pre[now]; } ans[rt]=now; } } int main() { int m; scanf("%d",&m); for(int i=1;i<m;i++) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } dfs(1,0); for(int i=1;i<=m;i++) { vector<int>put; put.push_back(ans[i]); if(size[ans[i]]*2==size[i]) put.push_back(pre[ans[i]]); sort(put.begin(),put.end()); for (int j = 0; j < put.size(); j++) { if(j)putchar(' '); printf("%d", put[j]); } printf("\n"); } }