题目链接：https://vjudge.net/problem/POJ-3107
题意：求树的可能的重心，升序输出。
思路：因为学树形dp之前学过点分治了，而点分治的前提是求树的重心，所以这题就简单水了一下。用sz[u]记录子树u的大小，son[u]记录以u为根时，子结点中最大的结点数。所以：
son[u]=max(son[v],n-sz[u])，前一部分son[v]好理解，对于n-sz[u]，即结点u的父结点那一块的大小。
AC code:
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn=;
int n,cnt,head[maxn],sz[maxn],son[maxn]; struct node1{
int v,nex;
}edge[maxn<<]; struct node2{
int val,id;
}ans[maxn]; void adde(int u,int v){
edge[++cnt].v=v;
edge[cnt].nex=head[u];
head[u]=cnt;
} bool cmp(node2 a,node2 b){
if(a.val==b.val) return a.id<b.id;
return a.val<b.val;
} void getroot(int u,int fa){
sz[u]=,son[u]=;
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].v;
if(v==fa) continue;
getroot(v,u);
sz[u]+=sz[v];
son[u]=max(son[u],sz[v]);
}
son[u]=max(son[u],n-sz[u]);
ans[u].val=son[u],ans[u].id=u;
} int main(){
scanf("%d",&n);
for(int i=;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
getroot(,);
sort(ans+,ans+n+,cmp);
printf("%d",ans[].id);
for(int i=;i<=n&&ans[i].val==ans[].val;++i)
printf(" %d",ans[i].id);
printf("\n");
return ;
}