[CSP-S2019] 树的重心

我们令任一重心作为根，分类统计。

一棵树的重心要么是根，要么在重儿子内，换言之，在重链上。

那么每个子树的重心可以均摊 $O(1)$ 地从其重儿子子树重心开始向上寻找。

对于一整棵树去掉一个子树后剩余的连通块，分类讨论：

如果删掉的部分不在重儿子内，此时删掉的部分大小相同，剩下部分重心一定相同。所以我们只需要从小到大枚举删掉部分的大小，同时向上移动整棵树的重心，时间复杂度 $O(n)$。另统计出轻儿子子树内，某个大小的子树各有多少棵。

如果删掉部分在重儿子内，而删掉后重儿子仍然是重儿子，剩余部分的重心仍然在重链上，并且一定不比原重心低，只能是根。

否则次重儿子会成为重儿子。此时类似地统计出删除重儿子内某个大小的子树后重心是谁，以及重儿子内某个大小的子树各有多少颗。