树的重心
Tarsal
·
·
个人记录
树的重心
定义
树上一节点，且满足它的最大子树的节点数最小。
性质
$1.$ 删除重心后所得的所有子树，节点数不超过原树的 $\frac{1}{2}$，一棵树最多有 $2$ 个重心；
证明：这是树的重心的基本性质，如果重心的一个子树的节点数大于 $\frac{1}{2}$ 那么重心的这个子儿子肯定会比重心更有资格当重心，矛盾。
$2.$ 树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等；
证明：这种情况只有可能是 $2$ 个重心之间连边，并且重心 $1$ 的最大子树是以重心 $2$ 为儿子的子树，重心 $2$ 的最大子树也是以重心 $1$ 为儿子的子树。 $2$ 个子树大小相等，各为 $\frac{n}{2}
证明，这个可以用反证法。假设我们取极限情况。一个重心连的最大子树大小为 $\frac{n}{2}$，另一个大小为 $1$。因为如果新的重心不在 $2$ 个重心之间，它也会在最大的子树的儿子节点。那么此时这个儿子所连的子树总大小（除了返祖的子树）为 $\frac{n - 1}{2}$ 那么可以可以简单容斥一下推出返祖的子树大小为 $n + 1 - \frac{n - 1}{2}$ 也就是 $\frac{n + 3}{2}$ 大于 $\frac{n}{2}$ 所以矛盾。
$4.$ 树删除或添加一个叶子节点，重心最多只移动一条边；
证明：这个很简单，因为一个节点被修改最多只会改变一个子树的大小。所以重心最多只能移动一位。
### 实现
首先是根据他的定义直接用 $Dfs$ 实现。
```
int size[maxn], val[maxn], f[maxn];//size[i] 表示 i 的子树大小，val[i] 表示 i 节点的权值，f[i] 表示 i 为根节点的最大子树。
void Dfs(int x, int fa) {
size[x] = val[x], f[x] = 0;
Next(i, x) { int v = e[i].to;
if(v == x) continue;
Dfs(v, x);
size[x] += size[v];
f[x] = max(f[x], size[v]);
} f[x] = max(f[x], n - size[now]);//要考虑它父节点引出去的
if(f[x] < f[ans]) ans = x;
}
```