转载：pyqpyq 的Blog

定义

一棵树中以一个节点为根的子树的大小的最大值最小的节点为树的重心。

性质一

一棵树中以重心为根的节点的子树大小均不超过整棵树的大小的一半。

证明：

考虑反证法。

假设一棵树中以重心为根的节点的子树大小有子树超过整棵树的大小的一半。

则以超过整棵的大小的一半的子树的根换为整棵树的根。

以原根为根的子树大小一定不超过整棵树的一半。

若其它子树的大小最大值不超过整棵树大小的一半，则现在的根的子树大小的最大值不超过整棵树大小的一半。

而以树的重心为根的子树大小的最大值不超过整棵树大小的一半。

则以树的重心为根的子树大小的最大值不是最小的，与定义矛盾。

若其它子树的大小最大值超过整棵树大小的一半，则继续以以超过整棵树的大小的一半的子树的根为整棵树的根。

由于每次换根都在往下走，所以肯定可以换到叶子节点或者在中间出现矛盾。

而到叶子节点时也可如上述过程推出矛盾。

所以必然矛盾，假设不成立。

所以一棵树中以重心为根的节点的子树大小均不超过整棵树的大小的一半。

判定一

一棵树中以一个节点为根的子树的大小的最大值最小的节点为树的重心。

就是定义啊。

判定二

一棵树中如果以一个节点为根的子树大小均不超过整棵树的大小的一半，则它为树的重心。

当然也有人拿这条判定做定义的，不过没有区别。只是这样的话我不会证明性质二而已。

证明：

由题可知，若此节点的子树中任意选一个换为根，则含原根的子树的大小不小于整棵树的大小的一半。

则以此节点为根的节点的子树大小的最大值不小于整棵树的大小的一半。

而以原根为根的子树大小均不超过整棵树的大小的一半。

即以原根为根的节点的子树大小的最大值不超过整棵树的大小的一半。

故以原根为根的节点的子树大小的最大值一定最小。

所以一棵树中如果以一个节点为根的子树大小均不超过整棵树的大小的一半，则它为树的重心。

性质二

一棵树一定有重心且最多有两个重心。

证明：

由于一棵树中以一个节点为根的子树的大小的最大值肯定有最小值。

所以一棵树一定有重心。废话

若两个点同为重心。

根据判定二的证明，以它们根的子树大小的最大值相等且为整棵树大小的一半，即最大的子树的根为对方。

所以它们之间有边相连。

若有三个点为中心。

则这三个点两两之间都有边相连。

出现了三元环，不符合树的定义。

性质三

如果一个点不为重心，那么它有且仅有一个大于整棵树大小的一半的子树且整棵树的所有重心被包含在这棵子树内。

做这题时想到的。

证明：

首先，“且”字前面的是废话。否则根据判定二，假如没有，这个点就成重心了，和假设不符。假如有多个，这些子树的大小和会超过整棵树大小，部分大于整体了。

重点是后面这句“整棵树的所有重心被包含在这棵子树内”。

注意“所有”包括有两个重心的情况，因为根据前文分析，如果一棵树有两个重心，那么这两个重心一定是有边相连的。

如果它们分在不同子树内的话，就会形成一个环，不符合树的定义。

接下来我们把根换成重心试试。

根据重心的定义，当前重心的子树中包含当前节点的子树大小一定小于等于整棵树大小的一半。

那么除开这个子树的其他部分的大小也会大于等于整棵树大小的一半。

我们再把根换回去，那么这些部分一定会被浓缩进一棵子树，而重心也在这个部分内，且这棵子树大小大于整棵树大小的一半。

就算除了这些部分这棵子树里还有其它东西，也不会影响结果。