poj3107（树的重心，树形dp）

题目链接：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=50005;
int n,cnt,head[maxn],sz[maxn],son[maxn];

struct node1{
    int v,nex; 
}edge[maxn<<1];

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]=1,son[u]=0;
    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=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        adde(u,v);
        adde(v,u);
    }
    getroot(1,0);
    sort(ans+1,ans+n+1,cmp);
    printf("%d",ans[1].id);
    for(int i=2;i<=n&&ans[i].val==ans[1].val;++i)
        printf(" %d",ans[i].id);
    printf("
");
    return 0;
}