树的重心

什么是树的重心？

树上选取一个点，使得最大的子树大小最小的点叫做重心。

重心有很多优美的性质，求重心是容易的，不再阐述。

• 1.以重心为树根时，最大的子树的大小不超过全树大小的一半，同时条件是充要的

对于充分性：
考虑调整法。不妨现在钦定一个重心 \(u\) 作为树根，有一个儿子 \(v\) 且 \(siz_v>\frac{n}{2}\)，那么，将重心(根节点)移动到这个子树内是一定不劣的，因为 \(n-siz_v<siz_v\)，所以 \(n-siz_v\le \frac{n}{2}\)，不难发现一直调整即可。

对于必要性：
考虑一个点 \(u\) 满足最大的子树的大小不超过全树大小的一半。
那么，只要去往任意一个儿子 \(v\) ，最大子树大小会变成 \(n-siz_v\)，所以这个子树内不会产生重心，除非 \(siz_v=\frac{n}{2}\)。如果不考虑这个情况的话，发现 \(u\) 是无法调整的，也就是重心。能调整的话只有 \(siz_v=\frac{n}{2}\) 的情况，而且只能调整一步。换句话说，这两个点都是重心。顺便证明了一条性质：

• 2.一颗树最多只有两个重心，且这两个重心一定是相邻的。此时树一定有偶数个节点，且可以被划分为两个大小相等的分支，每个分支各自包含一个重心。

• 3．一棵树的重心一定在根节点所在的重链上。

由 \(1\) 证明得到。上面的过程就是一直在跳重链。

• 4.如果树的所有边权都为 \(1\)，那么树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。反过来，距离和最小的点一定是重心。

考虑钦定根节点为这个距离最小的点，然后使用调整法，发现还是一个一直跳重链的过程，终止条件就是 \(n-siz_u>siz_u\)，也就是跳到重心了

• 5.在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

满足移动的条件是儿子 \(v\) 满足 \(siz_v>n-siz_v\)，所以它只会往这个方向移动至多一步。

• 6.把两棵树通过一条边相连得到一棵新的树，则新的重心在较大的一棵树一侧的连接点与原重心之间的简单路径上。如果两棵树大小一样，则重心就是两个连接点。
  另外一种说法：把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。

由 5 推出。