因为这道题令我十分兴奋，所以来写一下做完后的思考。
这道题用到了树的重心的种种性质，在写解法的时候会一一点出其用处。
首先，枚举每一条边，然后各自 \(O(n)\) 扫一次的 \(O(n^2)\) 做法是简单的。
那么接下来，就会出现不同的解法了：
优化 \(O(n)\) 求解的过程至 \(O(\log n)\)
利用 \(O(n)\) 状态 \(O(n)\) 求解的套路：枚举每一个的贡献。
那么接下来分开讲述两种做法
那么找一颗子树内的重心，就可以倍增求解了。
也就是删掉一个边 \((x, y)\) 之后（假定 \(y\) 是 \(x\) 的父亲）\(x\) 子树内的重心是简单的，但是子树外（也就是 \(y\) 所在的子树）的重心不太好求解。
类似换根 DP 的思路，发现 \(y\) 所在子树的倍增数组，只会影响到 \(y\) 到根路径上的每一个点。
于是每一次 DFS 下去，\(O(\log n)\) 的更新倍增数组，然后 \(O(\log n + \log n)\) 的求两边的重心即可。
此时我们需要考虑的是一个点 \(x\) 如何变成重心。
删除 \(x\) 子树中的某棵子树
删除 \(x\) 子树外的某棵子树
保留某一棵包含 \(x\) 子树
如果可以稍微合并一下，那么第二点和第三点是可以放在一起的。
但是如此分类讨论是相当难做的，考虑如何减少某一种状态。
同理的，删除一棵子树，那么重心会向相离的方向移动。
那么删除 \(x\) 子树内的某棵子树，\(x\) 能够成为重心必须满足重心在 \(x\) 的子树内。
那么如果我们以某一个重心为根，意味着除了根，那么就没有满足上述条件的点了，此时我们只需要讨论子树外的情况即可。
假设我们删除了大小为 \(s\) 的连通块，那么 \(x\) 可以成为重心则需要满足：
其中 \(siz_x\) 表示 \(x\) 所在子树的大小，\(mx_x\) 表示 \(x\) 子树的最大大小，也就是 \(mx_x = \max siz_y\)。
稍微整理一下，就可以得到：
那么考虑 \(x\) 子树外有那些满足此条件的子树即可。
但是发现 \(x\) 的祖先 \(f\) 的大小并不可以是 \(siz_f\)，而是 \(n - siz_f\)，这是在 DFS 的过程中好维护的。
最终利用树状数组维护一下即可。
但是重心本身的答案并不能如此维护，我们需要单独做一次。
设 \(X\) 为重心 \(G\) 作为根的最大的子树，\(Y\) 为次大子树，那么对于某个点 \(x\) 需要分类讨论一下：
这是容易 \(O(n)\) 做一次的。
于是此算法的复杂度为 \(O(n \log n)\)，代码应该不是很难。
可以参考代码内的注释：https://loj.ac/s/1911177
然而本算法仍然可以有优化的空间，可以参考 [CSP-S2019]树的重心 题解 - TEoS - 博客园，做到 \(O(n)\) 求解。
本题可以说是非常开放的题，因为存在很多解法，这里并没有涵盖完。
足以说明在 CSP 考试中，不能局限于某一个算法，更多的尝试可能带来更多的解法。
而在本题中体现出了解决问题的常用思想：
优化暴力 \(O(1) - O(n)\) 平衡为 \(O(n \log n) - O(\log n)\)，也就是算法 1。
多状态 \(O(n)\) 暴力求和转化为每一个元素的贡献。
利用信息所附带的信息（性质）推导方向，优化代码。
倍增！非常优秀的一个做法，是考点的长青树。这需要重重注意，细细揣摩。