树的重心
2019-08-19
概念
树的重心也叫树的质心。对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。
性质
1.树中所有点到某个点的距离和中，到重心的距离和是最小的（实际应用中经常用到此性质）。
2.把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
3.一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
4.一棵树最多有两个重心，且相邻。
Slove
求树的重心运用动态规划的思想，也就是树上跑DP。
先任选一个结点作为根节点，把无根树变成有根树，然后设d(i)表示以i为根的子树的结点的个数。不难发现d(i)=∑d(j)+1，j∈s（i）。s（i）为i结点的所有儿子结点的编号的集合。程序也十分简单：只需要DFS一次，在无根树有根数的同时计算即可，连记忆化都不需要——因为本来就没有重复计算。
那么，删除结点i后，最大的连通块有多少个呢？结点i的子树中最大有max{d（j）}个结点，i的“上方子树”中有n-d（i）个结点，
如图9-13。这样，在动态规划的过程中就可以找出树的重心了。
Tips
树的重点可以说是树的平衡点，其使以它为根的树中所有的子树的节点数相近。
Code
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=110; //N为节点数
int n,ans,res; //n——节点数，ans树的重心，res最大子树的节点数
int maxn=0x3fff;
int u,r;
int d[N];
vector<int> G[N];
void dfs(int s,int f){
d[s]=1;
int res=0;
for(int i=0;i<G[s].size();i++){
if(G[s][i]==f) continue;
dfs(G[s][i],s);
d[s]+=d[G[s][i]];
res=max(res,d[G[s][i]]);
}
res=max(res,n-d[s]);
if(res<maxn){
maxn=res;
ans=s;
}
/* 若选取序号较小的节点，可将代码更改成这样
if(res<maxn||(res==maxn&&ans>s)){
maxn=res;
ans=s;
}
*/
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&r);
G[u].push_back(r);
G[r].push_back(u);
}
dfs(1,0);
printf("%d",ans);
return 0;
}