CF708C Centroids

对于一个不是重心的点 \(u\)，它必定有一棵子树 \(T\) 包含所有重心（如果有两个重心则它们必定相邻），显然 \(|T|>\lfloor\frac{n}{2}\rfloor\)，这阻碍了它成为重心。贪心地想，我们要在 \(T\) 中找出一棵子树 \(S\) 使得 \(|S|\leq\lfloor\frac{n}{2}\rfloor\) 且 \(|S|\) 尽可能大，然后将 \(S\) 割掉接在 \(u\) 上。

其次 \(S\) 肯定是重心的某棵子树（分一个重心和两个重心讨论下），且肯定是重心最大或次大的子树，因为 \(u\) 最多只能被包含在其中的一棵子树中。

那么就很简单了，最多两个重心，最多四种选择，选最大且不包含 \(u\) 的割，判断是否合法即可。

可以用 DFS 序的左右边界以及是子树内还是子树外来表示无根树的一棵子树。