定义及性质
定义1：找到一个点,删除它得到的森林中最大的子树节点数最少（也就是最大的连通块的点数最小）,那么这个点就是这棵树的重心。
定义2：删除重心后得到的所有子树，其顶点数必然不超过n/2
性质1：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
性质2：把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
性质3：把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

一般我们树形dp一下就能求出树的重心，我们用 dp[x] 表示 x 点的子树的节点数量，然后dfs一遍就可以了。

POJ 1655 Balancing Act

题目大意：求出树的重心，若有多个，输出最小的重心编号。

AC代码：

#pragma GCC optimize(2)
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=4e4+10;
int T,n,dp[N],res;//dp[x]为x的孩子的个数 
int head[N],nex[N],to[N],tot,id;
void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int pre){
	int cnt=0,k=0;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==pre)	continue;
		dfs(to[i],x);
		dp[x]+=dp[to[i]]+1;	k=max(dp[to[i]]+1,k);
	}
	cnt=max(k,n-dp[x]-1);
	if(cnt<res||cnt==res&&x<id){
		res=cnt;	id=x;
	}
}
signed main(){
	cin>>T;
	while(T--){
		memset(dp,0,sizeof dp);
		cin>>n;	tot=0;	memset(head,0,sizeof head);	res=0x3f3f3f3f;
		for(int i=1;i<n;i++){
			int a,b;	cin>>a>>b;	add(a,b);	add(b,a);
		}
		dfs(1,-1);
		cout<<id<<' '<<res<<endl;
	}
	return 0;
}

POJ 3107 Godfather
题目大意：求出所有的树的重心编号，并按字典序排序输出。
AC代码：

#pragma GCC optimize(2)
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,dp[N],res,idx;
int head[N],nex[N],to[N],tot;
struct node{
	int x,id;
}v[N];
int cmp(node a,node b){
	if(a.x==b.x)	return a.id<b.id;
	else	return a.x<b.x;
}
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int pre){
	int cnt=0;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==pre)	continue;
		dfs(to[i],x);
		dp[x]+=dp[to[i]]+1;	cnt=max(cnt,dp[to[i]]+1);
	}
	v[idx++]={max(cnt,n-1-dp[x]),x};
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int a,b;	scanf("%d %d",&a,&b);	add(a,b);	add(b,a); 
	}
	dfs(1,-1);
	sort(v,v+n,cmp);
	for(int i=0;i<n;i++){
		if(i&&v[i].x!=v[i-1].x)	break;
		printf("%d ",v[i].id);
	}
	puts("");
	return 0;
}