更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19346416

首先考虑 $\mathcal{O}(n ^ 2)$ 的解法。

枚举每条边，然后分别统计左右子树的重心，然后想加即可。

然后考虑优化，显然我们的复杂度浪费在了找重心的地方。

“一棵有根树的重心一定在根结点所在的重链上。一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。”——OIwiki

有关树的重心的内容见OI-wiki/树的重心

重心必在节点的「重儿子链」上（重儿子指子树大小最大的子节点），因此可通过倍增沿重儿子链快速定位重心候选。

删除边 $(u, v)$ 后，$u$ 所在的大子树（大小 $n - sz_v$）需要「换根」更新重儿子（原重儿子可能是 $v$，需替换为次重儿子或父方向），而 $v$ 所在的小子树（大小 $sz_v$)）是原树的子树，无需换根。

节点最大子树（含父方向）≤ 总大小 / $2$ 则为重心。

递归算每个节点的子树大小，记录重 / 次重儿子（子树最大 / 次大的子节点），构建倍增数组（沿重儿子链跳，$\mathcal{O}(\log n)$ 找重心）。

然后累加答案即可。