本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-07 16:53:22

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

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

考虑 $m$ 是怎么来的。我们设 $(w, v)$ 是被删掉的边（$v$ 更深），两种情况：

• $v$ 和 $u$ 在同一条链上，那么 $m = n - s_v$
• 否则，$m = s_v$

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

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

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

• 删掉的 $v$ 在重儿子子树上，那么要求次重链的长度 $2h' \le n - s_v$
• 否则，$2h \le n - s_v$