Centroids

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

## Two Centroids 先考虑对于一棵树，至少要加多少个点才能有两个重心。 以重心为根，设最大儿子的子树大小为 $mx$，那么答案就为 $(n - mx) - mx = n - 2mx$。 接下来考虑如何在加点时维护最大子树，一个显然的性质，加一个点重心最多偏移一位，如果重心偏移，那么 $ ......

CF708C Centroids 一道换根 DP。 我们可以先找出树的一个重心，那么对于其他所有不是重心的点，它不能成为重心时因为它父亲的那一支节点数大于一半，而可以改造成功，则意味着可以在他父亲那一支里，可以找到子树u，使 $siz[u] \le n/2 && siz[fa]-siz[u] \le ......

洛谷传送门 CF 传送门 考虑固定一个重心，设 $k$ 为重心最大子树大小，答案为 $n - 2k$。构造方法是往最大的子树塞叶子。 树的重心有一个很好的性质，就是加一个叶子，重心最多移动一条边的距离。简单证一下，设重心为 $x$，往儿子 $u$ 的子树中加叶子。 如果 $sz_u > \left\ ......

题意： 给定一颗树，你有一次将树改造的机会，改造的意思是删去一条边，再加入一条边，保证改造后还是一棵树。 请问有多少点可以通过改造，成为这颗树的重心？（如果以某个点为根，每个子树的大小都不大于$\dfrac{n}{2}$，则称某个点为重心） 思路： 是今天遇到的一道有意思的换根dp呃呃。 从题意来看 ......