树的重心

部分转载自：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

上一篇：[luoguP1364] 医院设置（树的重心）

下一篇：[luoguP2420] 让我们异或吧（dfs + 异或的性质）

---

模板 树的重心