poj 1655 Balancing Act 树的重心

题目链接：http://poj.org/problem?id=1655

树的重心板子题

#include<iostream>
using namespace std;
#define maxn 20005
int t,n,cnt,root,maxx,head[maxn<<1],f[maxn],size[maxn];
struct edge{
    int next,to;
}e[maxn<<1];
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void getroot(int now,int fa)
{
    size[now]=1;f[now]=0;//f也是size 
    for(int i=head[now];i;i=e[i].next)
    {
        if(e[i].to!=fa)
        {
            getroot(e[i].to,now);
            size[now]+=size[e[i].to];
            f[now]=max(f[now],size[e[i].to]);
        }
    }
    f[now]=max(f[now],n-size[now]);
    if(f[now]<maxx)
    {
        root=now;
        maxx=f[now];
    }
    if(f[now]==maxx&&now<root)
    root=now;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        head[i]=0;
        int u,v;
        cnt=0;maxx=999999999,root=999999999;
        for(int i=1;i<n;i++)
        {
            cin>>u>>v;
            add(u,v);add(v,u);
        }
        getroot(1,0);
        cout<<root<<" "<<maxx<<endl;
    }
    return 0;
}