树的重心

概念

在一棵 $n$ 个节点的树上，删去节点 $v$ 后，树会分裂成若干连通分量；如果每个连通分量的大小都不超过 $\lfloor \frac{n}{2}\rfloor$，则称 $v$ 是这棵树的重心。

删去重心后得到的若干子树大小均不超过 $\lfloor \frac{n}{2}\rfloor$，这使重心成为点分治等树上分治算法中"每次把问题规模减半"的理想划分点。重心可能不唯一（例如一条边把树恰好等分时，两个端点都是重心），但重心之间关系密切，见下面的性质。

相关性质

先约定记号：

• $T_x(y)$：删去边 $(x,y)$ 后，含 $y$ 的连通分量大小（即以 $x$ 为根时 $y$ 的子树大小）；
• $W(x)=\underset{y\sim x}{max}{T}_x(y)$：删去 $x$ 后最大的连通分量大小；
• $S(x)=\sum _{u\in T}d(u,x)$：所有节点到 $x$ 的距离和。

显然，重心的定义就是 $W(x)\le \lfloor \frac{n}{2}\rfloor$。

先指出一个树的基本事实：删去任意节点 $x$ 后，$x$ 与每个连通分量之间恰好有一条边。否则，若某个分量 $B$ 中有两个节点都直接与 $x$ 相连，则 $B$ 内这两点间的唯一路径加上这两条边就构成了环，与树矛盾。

性质一：三个等价定义

以下三个条件等价：

1. $W(x)\le \lfloor \frac{n}{2}\rfloor$（重心定义）；
2. $W(x)$ 在所有节点中最小；
3. $S(x)$ 在所有节点中最小（距离和最小）。

证明：

先证 $1⟺2$。

• $1\Rightarrow 2$：设 $W(x)\le \lfloor \frac{n}{2}\rfloor$。对任意 $y\ne x$，删去 $x$ 后 $y$ 所在连通分量记为 $B$，$|B|\le \lfloor \frac{n}{2}\rfloor$。删去 $y$ 后，含 $x$ 的连通分量至少包含 $T\setminus B$ 与 $x$，大小 $\ge n-|B|\ge \lceil \frac{n}{2}\rceil \ge \lfloor \frac{n}{2}\rfloor \ge W(x)$，故 $W(y)\ge \lfloor \frac{n}{2}\rfloor \ge W(x)$。由 $y$ 的任意性，$W(x)$ 最小。
• $2\Rightarrow 1$：反证。若 $W(x)>\lfloor \frac{n}{2}\rfloor$，设删去 $x$ 后最大的连通分量为 $B$（$|B|>\lfloor \frac{n}{2}\rfloor$，从而 $|B|>\frac{n}{2}$），$y$ 是 $B$ 中与 $x$ 相邻的唯一点（由上面的树的事实）。删去 $y$ 后，含 $x$ 的连通分量大小恰为 $n-|B|<\frac{n}{2}$，$B$ 内部其余各分量均 $\le |B|-1$，于是 $W(y)\le max(n-|B|,|B|-1)<|B|=W(x)$，与 $W(x)$ 最小矛盾。

再证 $1⟺3$。先建立换根公式：对相邻点 $x,y$，把"根"从 $y$ 换到 $x$ 时，$y$ 侧 $T_x(y)$ 个节点到 $x$ 比到 $y$ 远 $1$，其余 $n-T_x(y)$ 个节点到 $x$ 比到 $y$ 近 $1$，所以

$S(x)-S(y)=T_x(y)-(n-T_x(y))=2T_x(y)-n.$

• $1\Rightarrow 3$：若 $W(x)\le \lfloor \frac{n}{2}\rfloor$，则对 $x$ 的每个邻点 $y$ 都有 $T_x(y)\le \lfloor \frac{n}{2}\rfloor \le \frac{n}{2}$，代入换根公式得 $S(x)\le S(y)$，即 $S$ 在 $x$ 的邻域内取最小。沿任意路径 $x_0\to x_1\to \cdots \to x_k$，$T_{x_i}(x_{i+1})$ 随 $i$ 严格递减（$x_{i+2}$ 侧的分量被 $x_{i+1}$ 侧的分量严格包含），所以 $S$ 沿路径先不增、后不降（单峰），邻域最小即全局最小。故 $S(x)$ 最小。
• $3\Rightarrow 1$：反证。若存在 $x$ 的邻点 $y$ 使 $T_x(y)>\frac{n}{2}$，由换根公式 $S(y)-S(x)=n-2T_x(y)<0$，即 $S(y)<S(x)$，与 $S(x)$ 最小矛盾。

三个定义等价得证。这也说明：求重心既可以从"最大连通分量最小"出发，也可以从"距离和最小"出发，两种求法见下文。

性质二：重心至多两个；若有两个则相邻，且删去它们的连边后树被等分

证明：设 $x$ 是重心。

• 若 $W(x)<\frac{n}{2}$：对任意 $y\ne x$，删去 $x$ 后 $y$ 所在分量 $B$ 满足 $|B|\le W(x)<\frac{n}{2}$。删去 $y$ 后，含 $x$ 的分量大小 $\ge n-|B|>\frac{n}{2}$，故 $W(y)>\frac{n}{2}>W(x)$，$y$ 不是重心。此时重心唯一。
• 若 $W(x)=\frac{n}{2}$：删去 $x$ 后恰有一个分量 $B$ 大小为 $\frac{n}{2}$（其余分量之和为 $\frac{n}{2}-1$，均小于 $\frac{n}{2}$）。设 $y$ 是 $B$ 中与 $x$ 相邻的唯一点。删去 $y$ 后，含 $x$ 的分量大小为 $n-|B|=\frac{n}{2}$，$B\setminus \{y\}$ 的各分量均 $<\frac{n}{2}$，故 $W(y)=\frac{n}{2}$，$y$ 也是重心。而对其他节点 $z$：若 $z$ 不在 $B$ 中，删去 $z$ 后 $B\cup \{x\}$ 侧大小 $\ge \frac{n}{2}+1>\frac{n}{2}$；若 $z\in B\setminus \{y\}$，删去 $z$ 后含 $x$ 的分量至少包含 $y$（$y$ 仍与 $x$ 相邻），大小 $\ge \frac{n}{2}+1$。所以其他节点都不是重心，重心恰为 $x,y$ 两个，它们相邻，且删去边 $(x,y)$ 后两个连通分量大小均为 $\frac{n}{2}$。

性质三：添加或删除一个叶子，重心至多移动一条边

证明（以添加叶子为例，删除叶子对称）：

• 原树只有唯一重心 $v$。由性质二，此时必有 $W(v)<\frac{n}{2}$，故删去 $v$ 后任意分量 $B_p$ 满足 $|B_p|<\frac{n}{2}$。新叶子 $x$ 挂在 $B_p$ 内，新树中该分量变为 $B_p\cup \{x\}$，大小 $|B_p|+1\le \lceil \frac{n}{2}\rceil \le \frac{n+1}{2}$，不超过新树节点数的一半，$v$ 仍是新树的重心。
• 原树有两个重心 $u,v$，删去边 $(u,v)$ 后两分量等大（各 $\frac{n}{2}$）。若新叶子 $x$ 挂在 $v$ 侧分量内：删去 $u$ 后含 $v$ 侧大小为 $\frac{n}{2}+1>\frac{n+1}{2}$，$u$ 不再是重心；删去 $v$ 后各分量仍 $\le \frac{n}{2}\le \frac{n+1}{2}$，$v$ 仍是重心（新树节点数为奇数，重心唯一）。挂在 $u$ 侧时对称。

综上，新树的重心一定在旧树重心与新叶子的路径上，至多移动一条边。

性质四：两棵树用一条边相连，新树重心在两树重心连线的路径上

证明思路（归纳）：设 $T_1,T_2$ 的重心分别为 $c_1,c_2$，用边 $(x,y)$（$x\in T_1$，$y\in T_2$）把两棵树连成新树 $T$。对 $T$ 中不在路径 $c_1\sim c_2$ 上的节点 $z$，把它沿"靠近 $c_1$ 或 $c_2$ 的方向"移动一步，删去移动后的节点得到的最大连通分量不会增大——因为 $c_1$（或 $c_2$）已经是 $T_1$（或 $T_2$）内部最优的划分点，而跨树的那一侧分量的大小只取决于移动是否跨越桥边。反复移动后，重心可以在路径 $c_1\sim c_2$ 上取到。严格证明可用对 $|T_1|+|T_2|$ 的归纳，见 OI Wiki。

性质五：有根树中，重心在根的重链上；重心是其重子节点子树重心的祖先

设以 $r$ 为根，$v$ 是 $r$ 的最大子节点（重子），即 $siz[v]$ 是 $r$ 所有真子树大小的最大值。

证明：

• 若 $siz[v]\le \lfloor \frac{n}{2}\rfloor$：删去 $r$ 后最大连通分量恰为 $siz[v]\le \lfloor \frac{n}{2}\rfloor$，$r$ 是重心。
• 若 $siz[v]>\frac{n}{2}$：对任意不在 $v$ 子树内的节点 $z$，删去 $z$ 后含 $v$ 的连通分量大小 $\ge siz[v]>\frac{n}{2}$，$z$ 不是重心，重心必在 $v$ 的子树内。对 $v$ 的子树递归应用同样的结论，重心最终落在"从根沿重链一路向下"的路径上。

因此，整棵树的重心就是从根沿重链下降到第一个满足"最大连通分量 $\le \lfloor \frac{n}{2}\rfloor$"的节点，它也是重子节点对应子树的重心的祖先。这条性质给重心提供了第三种求法（见求法二末尾的补充）。

求法一：从定义出发（DFS 统计子树大小）

任选一个根（如 $1$）做一次 DFS，求出每棵子树的大小 $siz[u]$。删去 $u$ 后的连通分量包括：各子节点 $v$ 的子树（大小 $siz[v]$）和"向上"的部分（大小 $n-siz[u]$），所以

$W(u)=max(\underset{v\in son(u)}{max}siz[v],n-siz[u]).$

由定义（性质一），重心就是 $W(u)$ 最小的节点，等价地是满足 $W(u)\le \lfloor \frac{n}{2}\rfloor$ 的节点。

完整代码（输出重心编号与删去它后最大连通分量的大小）：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 2 * N;
int h[N], e[M], ne[M], idx;
int siz[N];
bool st[N];
int n, best = N, center;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) {  // 返回以 u 为根的子树大小
    st[u] = true;
    siz[u] = 1;

    int mx = 0;  // 删去 u 后最大的连通分量大小
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (st[v]) continue;
        siz[u] += dfs(v);
        mx = max(mx, siz[v]);
    }
    mx = max(mx, n - siz[u]);  // "向上"的连通分量

    if (mx < best) {
        best = mx;
        center = u;
    }

    return siz[u];
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    dfs(1);

    cout << center << ' ' << best << endl;

    return 0;
}

复杂度 $O(n)$，空间 $O(n)$。

从定义出发时也可以这样求树的重心：

假设树的节点总数为 $n$，任选一个节点作为树根将无根树转为有根树。设 $f[u]$ 代表以 $u$ 为根的子树的节点总数，由定义：删除重心后得到的所有子树中，每棵子树的节点总数均小于等于原树节点数目的一半。因此在搜索回溯时，若第一次出现 $f[u]\ast 2\ge n$，那么 $u$ 就是重心。

核心代码如下：

int n; // 树中节点总数
int ans; // 树的重心
int f[N]; // f[u] 代表以 u 为根的子树的节点总数
bool sym = false;

void dfs(int u, int fa) {
    f[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        dfs(v, u);
        f[u] += f[v];
    }

    if (f[u] * 2 >= n && !sym) {
        ans = u;
        sym = true;
    }
}

AcWing 846. 树的重心

题意：$n$ 个节点的树，求删去一个节点后剩余连通块大小的最大值的最小值。上面的代码即为其完整解法，仓库题解见 AcWing 846. 树的重心。

求法二：从性质出发（换根 DP 求距离和最小）

由性质一，距离和最小的节点就是重心。先以 $1$ 为根求出 $dp[u]$（$u$ 的子树内节点到 $u$ 的距离和），再用换根公式

$S(v)=S(u)-siz[v]+(n-siz[v])$

求出以每个节点为根时的距离和（$v$ 侧 $siz[v]$ 个节点距离各减 $1$，其余 $n-siz[v]$ 个节点距离各加 $1$），取最小值对应的节点。

完整代码（多个重心时取编号最小）：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 100010, M = 2 * N;
int h[N], e[M], ne[M], idx;
int siz[N];
LL dp[N], S[N];
int n;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs1(int u, int fa) {  // 求以 1 为根时各子树大小与子树内距离和
    siz[u] = 1;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        dp[u] += dp[v] + siz[v];  // v 子树内每个节点到 u 比到 v 远 1
    }
}

void dfs2(int u, int fa) {  // 换根
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        S[v] = S[u] - siz[v] + (n - siz[v]);
        dfs2(v, u);
    }
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    dfs1(1, 0);
    S[1] = dp[1];
    dfs2(1, 0);

    LL mini = (LL)4e18;
    int center = 0;
    for (int i = 1; i <= n; i++) {
        if (S[i] < mini || (S[i] == mini && i < center)) {
            mini = S[i];
            center = i;
        }
    }

    cout << center << ' ' << mini << endl;

    return 0;
}

复杂度 $O(n)$。

洛谷 P1395. 会议

题意：$n$ 个村庄形成一棵树，选一个村庄开会，使所有村民到会场的距离总和最小，若有多个最优解输出编号最小的。上面的换根 DP 代码即为其完整解法，仓库题解见 洛谷 P1395. 会议。

补充：利用性质五还可以"沿重链下降"求重心——从根出发，若当前节点的某个子树大小 $>\frac{n}{2}$ 就进入该子树，重复直到当前节点满足 $W(u)\le \lfloor \frac{n}{2}\rfloor$，停下的节点即重心；若它满足 $W(u)=\frac{n}{2}$（即树被某条边等分），则其最大子树方向上还有另一个重心。这同样只需一次 DFS 统计子树大小再沿最大子树行走，复杂度 $O(n)$。