一、什么是树的重心
所谓树的重心指的是删掉这个点之后可以使所有子树中大小最大的那一个最小。
树的重心满足一些性质：
- 性质 \(1\)：删掉树的重心之后，所有子树的大小不都超过 \(\lfloor\frac{n}{2}\rfloor\)，\(n\) 指树的节点数量。
- 性质 \(2\)：如果有两个树的重心，那么这两个点一定是一条边的两个端点。
- 性质 \(3\)：树的重心到树上所有点的路径数的和最小。
二、树的重心性质证明
1.性质 \(1\)
首先从性质 \(1\) 开始，直觉告诉我它是对的，首先要知道一个不需要证明的东西，就是如果连树的重心都无法满足性质 \(1\)，那其它点也无法满足性质 \(1\)，因为树的重心会使删掉这个点之后所有子树中大小最大的那一个最小，那么它肯定将所有子树分割的很均匀（学过贪心算法的人都知道吧），直白的讲就是把这些子树的大小分割的差不多，那么连这么分割都无法满足性质 \(1\)，那其它点就更不可能满足性质 \(1\) 了，好了，然后继续，那么假设我们虚拟一个树，设置它的重心为 \(x\)，如果 \(x\) 的子树中有一个的大小超过了 \(\lfloor\frac{n}{2}\rfloor\)（不可能有两个超过），其余的子树大小都小于 \(\lfloor\frac{n}{2}\rfloor\)，那么我们可以把树的重心 \(x\) 跳到它这个儿子上，那么这个子树的大小自然就缩小了，其余子树的大小自然就放大了，当然了，不可能出现这个子树的大小还没缩小到 \(\lfloor\frac{n}{2}\rfloor\) 其余最大的子树的大小就已经大于 \(\lfloor\frac{n}{2}\rfloor\) 了，因为这样一来这些子树的大小加起来都大于 \(n\) 了，性质 \(1\) 得证。
2.性质 \(2\)
然后就是性质 \(2\)，这个性质非常奇怪，直觉都告诉我似乎不对，因为如果有多个树的重心，那么说明此时从任何一个重心调整到另外一个重心不影响答案，那么只有可能这个重心一边是极限（\(\lfloor\frac{n}{2}\rfloor\)），一边是极限减 \(1\)（\(\lfloor\frac{n}{2}\rfloor-1\)），显然此时 \(n\) 一定是偶数，否则加在一起答案就不是 \(n\)，然后由于调整都是调整到儿子上，所以从这个重心跳到另外一个重心，它只需要经过一条边，那么此时重心就不可能有大于两个了，而且都是在一条边上，性质 \(2\) 得证。