树的重心

树的重心

定义

树上一节点，且满足它的最大子树的节点数最小。

性质

\(ps.\) 性质网上都有，但是没有一篇博客进行了证明。此后的儿子节点指重心与子树相连的节点。

\(1.\) 删除重心后所得的所有子树，节点数不超过原树的 \(\frac{1}{2}\)，一棵树最多有 \(2\) 个重心；

证明：这是树的重心的基本性质，如果重心的一个子树的节点数大于 \(\frac{1}{2}\) 那么重心的这个子儿子肯定会比重心更有资格当重心，矛盾。

\(2.\) 树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等；

证明：这种情况只有可能是 \(2\) 个重心之间连边，并且重心 \(1\) 的最大子树是以重心 \(2\) 为儿子的子树，重心 \(2\) 的最大子树也是以重心 \(1\) 为儿子的子树。 \(2\) 个子树大小相等，各为 \(\frac{n}{2}\)

\(3.\) 两个树通过一条边合并，新的重心在原树 \(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;
}