708C

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

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

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