---

树的重心：对于一颗n个节点的无根树，找到一个点，使得把树变成以该节点为根的有根树时，最大子树的节点数最小，也就是说删除这个点后最大联通块的节点数最小。

如果要以i为重心的话，那么其最大子树的节点数就是max(max(dp[j]), n - dp[i]),其中j为i的孩子节点。

树的重心的性质：

    性质 1 ：树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。

    性质 2 ：把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上。

    性质 3 ：一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。

dfs:树的重心模板：

int mins, id;
void dfs(int u, int father){
	dp[u] = 1;
	int maxs = 0;
	for (int i = h[u]; i; i = next_pos[i]){
		int j = e[i];
		if (j == father){
			continue;
		}
		dfs(j, u);
		dp[u] += dp[j];
		maxs = max(maxs, dp[v]);
	}
	maxs = max(maxs, n - dp[u]);
	if (maxs < mins){
		mins = maxs;
		id = u;
	}
}

------------------------------------------------------------

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int t, n;
int h[N], dp[N];//dp[N]表示以i为根节点的树的节点个数
int e[N], next_pos[N], idx;
void add(int a, int b...