部分转载自：blogsdn.net/u013076044/article/details/45915745
定义
找到一个点，其所有子树中最大的子树节点数最少，那么这个点就是整棵树的重心。
在树的总点数为偶数时，可能会有两个重心。
性质
性质 1 ：树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样。
性质 2 ：把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上。
性质 3 ：一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
求法
在找树的重心时，我们先随意确定一个根，之后通过一遍dfs将所有子树的大小求出来。
如果有一个点 i 满足 2 * size[i] >= n ，并且它的儿子都满足 2 * size[son[i]] <= n ，那么这个点就是树的重心。
至于代码有些不同。
1 inline void dfs(int u) 2 14 } 15 if(2 * size[u] >= tot && !ans) ans = u; 16 }View Code
上一篇：[POJ1797] Heavy Transportation（最大生成树 || 最短路变形）
下一篇：[HDU4417]Super Mario（主席树+离散化）
树的重心 模板
