树的重心 分析

· · 个人记录

我们首先用重心做根，那么有一个结论：将非根点 u 子树内的边断开，不可能让 u 是重心，用树的重心性质比较好证。

然后，我们设被删掉的另一部分的大小为 m，则 2h_u \le n - m 且 2(n - m - s_u) \le n - m，化简得到：

考虑 $m$ 是怎么来的。我们设 $(w, v)$ 是被删掉的边（$v$ 更深），两种情况： + $v$ 和 $u$ 在同一条链上，那么 $m = n - s_v

我们将所有 s 放到树状数组中，然后在 DFS 的过程中加入 n - s_v，DFS 结束时候删除，于是就可以得到答案。

怎么处理子树内的边？我们维护另一棵树状数组，然后计算进入进出子树的差值即可。

根的贡献需要特殊计算，我们分两种情况：