Balancing Act
题目链接：
http://poj.org/problem?id=1655
题意：
给出一棵树，求树的重心和以重心为根节点节点最多的子树的节点数，如果有多个重心输出编号较小的。
题解：
树的重心：找出一个节点v，以v为根，使得v的“节点最多的子树”的节点最少化
水题，随便以某个节点为根开始深搜，其中某节点v的“节点最多的子树”的节点数=min（sum[child[v]]，n-∑sum[child[v]]-1）
代码
#include<stdio.h>
const int N=2e4+1;
int cnt,head[N],Ev[N*2],Enext[N*2],res1,res2;
int Abs(int x)
{
return x>=0?x:-x;
}
void addedge(int u,int v)
{
Ev[cnt]=v;
Enext[cnt]=head[u];
head[u]=cnt++;
}
int Dfs(int id,int fa,int n)
{
int sum=0,mx=0;
for(int i=head[id];i!=-1;i=Enext[i])
{
int v=Ev[i];
if(v==fa)continue;
int w=Dfs(v,id,n);
sum+=w;
if(w>mx)mx=w;
}
sum++;
if(n-sum>mx)mx=n-sum;
if(mx<res2||(mx==res2&&id<res1))
{
res2=mx;
res1=id;
}
return sum;
}
void clean(int n)
{
cnt=0;
res2=n+1;
for(int i=1;i<=n;++i)
head[i]=-1;
}
void solve()
{
int T,n,x,y;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
clean(n);
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
Dfs(1,1,n);
printf("%d %d
",res1,res2);
}
}
int main()
{
solve();
return 0;
}