04.树的重心

本文介绍树的重心的概念和基本性质。

定义

如果在树 $T$ 中删去某个结点 $v$ 后，得到的图 $T ∖ {v}$ 中每个连通分量的大小均不超过原树结点数的一半，就称这个结点 $v$ 为整棵树的重心（centroid）。删去某一结点后得到的最大连通分量的大小也称为该结点的重量（weight）。利用这一概念，重心的定义可以叙述为重量不超过树结点数的一半的结点。

「子树」

本文可能同时涉及无根树、有根树，以及将有根树换根到非根结点得到的树。为了避免混淆，本文将用 $T$ 表示无根树，用 $T^{(v)}$ 表示以结点 $v$ 为根的有根树。本文中提到的「子树」均是指 有根树 中，一个结点及其所有子孙结点构成的树。有根树 $T^{(v)}$ 中，结点 $u$ 对应子树记为 $T_{u}^{(v)}$ 。这样定义的子树当然包括整棵树本身。如果要明确不包括整棵树本身，将称呼它为「真子树」。

无根树中的「子树」通常指它的一个连通子图。在讨论重心时，部分作者会用「子树」一词特指不包含某结点的极大连通子图，或者特指将某条边删去后得到的两个连通分量之一。容易验证，这两种方式定义得到的「子树」集合是一致的，且不包括整棵树自身。由于它和有根树的子树集合并不一致，本文将避免对无根树使用「子树」概念。

在实际求解重心或处理某些问题时，通常存在一个默认的树根。此时，将非根结点 $v$ 删掉得到的连通分量中，除了该结点的子结点对应子树外，还有一棵「向上」的子树。此时，设结点 $v$ 的父结点为 $u$ ，这棵「向上」的子树就是 $T_{u}^{(v)}$ 。本文在提及这类子图时，会显式地称呼它为「向上」的子树。若无特殊说明，本文提及的子树均不包括这类「向上」的子树。

注意到，得到的这些连通分量同样是无根树。通过删去树的重心，一棵树将变为若干棵至多原树一半大小的树。重心的这一特性使得在树上应用分治思想解决问题成为可能。这就是点分治，也称为树的重心分解。

性质

本节讨论重心的性质。首先，树的重心有如下等价定义：

等价定义

树 $T$ 中的结点 $v$ 是它的重心，当且仅当以下任意一条成立：

[list2tab]

无根树版本

在树中删去结点 $v$ 后，得到的图 $T ∖ {v}$ 中每个连通分量的大小均不超过原树结点数的一半。

在所有删去某个结点后得到的最大连通分量大小中，删去结点 $v$ 时所得到的值最小。

树中所有结点到某个结点的距离和中，到结点 $v$ 的距离和最小。

有根树版本

当树以结点 $v$ 为根时，任一真子树的大小均不超过原树结点数的一半。

在所有以某个结点为根时的最大真子树大小中，以结点 $v$ 为根时所得到的值最小。

在所有以某个结点为根时所有结点的深度和中，以结点 $v$ 为根时深度和最小。

[!note]- 证明

首先，引入一些记号。有根树和无根树两个版本的表述显然是等价的。定义 $W (x) = max_{u \sim x} ∣ T_{u}^{(x)} ∣$ ，其中， $u \sim x$ 表示 $u$ 和 $x$ 相邻。定义 $S (x) = \sum_{u \in T} d (u, x)$ ，其中， $d (u, x)$ 表示结点 $u$ 和 $x$ 之间的距离。那么，定义 1 相当于要求 $W (v) \leq ∣ T ∣/2$ ，定义 2 相当于要求 $v \in ar g min_{x \in T} W (x)$ ，定义 3 相当于要求 $v \in ar g min_{x \in T} S (x)$ 。需要证明的是，这三个条件是等价的。

将 $S (x)$ 理解为以 $x$ 为根时的结点深度和，考虑它在树根从结点 $v$ 换为相邻结点 $u$ 时发生的变化。注意到，在树中删去边 $(v, u)$ 后，得到的两个连通分量分别是子树 $T_{v}^{(u)}$ 和 $T_{u}^{(v)}$ 。在换根前后，子树 $T_{v}^{(u)}$ 中每个结点深度都增加 $1$ ，子树 $T_{u}^{(v)}$ 中每个结点深度都减少 $1$ ，所以，深度和的变化为
$Δ S_{v \to u} = S (u) - S (v) = ∣ T_{v}^{(u)} ∣ - ∣ T_{u}^{(v)} ∣ = ∣ T ∣ - 2∣ T_{u}^{(v)} ∣.$
所以，定义 1 的条件相当于要求 $Δ S_{v \to u} \leq 0$ 对 $v$ 的所有相邻结点 $u$ 都成立，也就是说， $v$ 是 $S (x)$ 的极小值点。

转而设 $v$ 是 $S (x)$ 的（一个）最小值点（即定义 3），它必然存在，且一定是极小值点。考虑以 $v$ 为根的有根树 $T^{(v)}$ 。设 $u \neq = v$ 是一个非根结点，且从 $v$ 到 $u$ 的有向路径上，结点 $v$ 的后一个结点为 $y$ （可能就是 $u$ ），结点 $u$ 的前一个结点为 $x$ （可能就是 $v$ ）。那么，因为 $T_{u}^{(x)} \subseteq T_{y}^{(v)}$ ，所以有
$2∣ T_{x}^{(u)} ∣ = 2∣ T ∣ - 2∣ T_{u}^{(x)} ∣ \geq 2∣ T ∣ - 2∣ T_{y}^{(v)} ∣ \geq ∣ T ∣.$
其中，最后一步用到 $v$ 是 $S (x)$ 的极小值点这一事实。此时，有两种情形：

存在结点 $u$ 使得 $2∣ T_{x}^{(u)} ∣ = ∣ T ∣$ 成立。此时，根据上述不等式，必然有 $(x, u) = (v, y)$ ，且 $∣ T_{v}^{(u)} ∣ = ∣ T_{u}^{(v)} ∣ = ∣ T ∣/2$ 。也就是说，使得等式成立的结点 $u$ 只能有一个，且它必然与 $v$ 相邻。此时，对于所有其他结点 $u^{'} \neq = u, v$ ，必然存在 $x^{'} \sim u^{'}$ 使得 $∣ T_{x^{'}}^{(u^{'})} ∣ > ∣ T ∣/2$ 成立。满足条件 1 的结点集合为 ${v, u}$ 。

注意到，删去任何结点时，得到的连通分量大小之和总是 $∣ T ∣ - 1$ ，所以，只要有一个连通分量大小不小于 $∣ T ∣/2$ ，它就必然是最大连通分量。因此，对于这种情形， $W (v) = W (u) = ∣ T ∣/2$ ，且对于所有 $u^{'} \neq = u, v$ 都有 $W (u^{'}) > ∣ T ∣/2$ 。因此，满足条件 2 的结点集合为 $ar g min W (x) = {v, u}$ 。

又因为 $Δ S_{v \to u} = 0$ ，所以 $S (v) = S (u)$ 。因为 $v$ 是最小值点， $u$ 也一定是最小值点。而对于 $u^{'} \neq = u, v$ 都存在 $x^{'} \sim u^{'}$ 使得 $∣ T_{x^{'}}^{(u^{'})} ∣ > ∣ T ∣/2$ ，这违反了极小值点需要满足的条件，所以， $u^{'}$ 一定也不是最小值点。因此，满足条件 3 的结点集合为 $ar g min S (x) = {v, u}$ 。

不存在结点 $u$ 使得 $2∣ T_{x}^{(u)} ∣ = ∣ T ∣$ 成立。此时，对于所有结点 $u \neq = v$ ，都存在结点 $x \sim u$ 使得 $∣ T_{x}^{(u)} ∣ > ∣ T ∣/2$ 。重复前文分析可知，对于所有结点 $u \neq = v$ ，都有 $W (u) > ∣ T ∣/2$ ，且 $u$ 不是 $S (x)$ 的极小值点。因此，满足条件 1 的结点只有 $v$ ，且 $ar g min W (x) = ar g min S (x) = {v}$ 。

无论在哪一情形中，满足三个条件的集合都是相同的。这就证明了三个定义是等价的。

除了这些等价定义外，树的重心还有如下常见性质：

性质

树的重心如果不唯一，则恰有两个。这两个重心相邻。而且，删去它们的连边后，树将变为两个大小相同的连通分量。

在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

把两棵树通过一条边相连得到一棵新的树，那么新树的重心在连接原来两棵树的重心的路径上。

一棵有根树的重心一定在根结点所在的重链上。一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。

证明

性质 1 可以从对重心等价定义的证明中得到。

性质 2 只需要考虑添加一个叶子结点的情形。这进一步分为两种情形：

树 $T$ 只有一个重心 $v$ 。设 $x$ 为新添加的叶子结点，且在新树中删去结点 $v$ 得到的图 $T \cup {x} ∖ {v}$ 中， $x$ 所在连通分量为 $B \cup {x}$ 。因为 $v$ 是树 $T$ 的唯一重心，所以 $2∣ B ∣ < ∣ T ∣$ ，也就是 $2∣ B ∣ + 1 \leq ∣ T ∣$ 。进而，有
$2∣ B \cup {x} ∣ = 2 (∣ B ∣ + 1) \leq ∣ T ∣ + 1 = ∣ T \cup {x} ∣.$
因此， $v$ 仍然是新树 $T \cup {x}$ 的重心。即使新树的重心不唯一，它也必然是 $v$ 的相邻结点。因此，重心至多移动一条边。

树 $T$ 有两个重心 $u, v$ 。此时，删去 $(u, v)$ 得到的两个连通分量 $T_{u}^{(v)}$ 和 $T_{v}^{(u)}$ 大小相等，均为 $∣ T ∣/2$ 。不妨设新添加的叶子结点 $x$ 连接在 $v$ 所在的连通分量 $T_{v}^{(u)}$ 上。那么，因为
$∣ T_{v}^{(u)} \cup {x} ∣ = ∣ T ∣/2 + 1 > (∣ T ∣ + 1) /2 = ∣ T \cup {x} ∣/2,$
所以 $u$ 不再是新树的重心。反过来，因为删去 $v$ 后，仍然有大小为 $∣ T ∣/2$ 的连通分量 $T_{u}^{(v)}$ ，而其他连通分量的大小之和为
$∣ T \cup {x} ∣ - 1 - ∣ T_{u}^{(v)} ∣ = ∣ T ∣/2 \leq ∣ T_{u}^{(v)} ∣,$
所以， $v$ 仍然是新树的重心。因为新树的结点数是奇数，重心必然唯一。所以，重心也至多移动一条边。

总结两种情形的分析可以发现，新树的重心一定在旧树的重心与新添加的叶子结点的路径上。

性质 3 可以通过归纳法说明。设 $T$ 和 $T^{'}$ 连接时，新添加的边为 $(x, y)$ ，且 $x \in T, y \in T^{'}$ 。不妨设新树的（一个）重心在 $T$ 中。考虑从树 $T$ 开始，将树 $T^{'}$ 中结点逐一添加为其叶子结点的过程。可以归纳地证明，树的（一个）重心始终在连接树 $T$ 的重心与结点 $x$ 的路径上。归纳起点显然。假设直到某一时刻为止，命题仍然成立。设此时重心为 $v$ 。由性质 2 的分析可知，新树的重心必然在连接新添加结点和当前重心 $v$ 的路径上，又因为它不会移动到树 $T$ 外，所以，只需要考虑路径与树 $T$ 的公共部分，即连接当前重心 $v$ 和结点 $x$ 的路径上。根据归纳假设， $v$ 就在连接树 $T$ 的重心和结点 $x$ 的路径上，所以，新树重心也必然在连接当前重心 $v$ 和结点 $x$ 的路径上。由归纳法可知，命题成立。

性质 4 只需要结合重链剖分性质即可说明。设树 $T$ 的（一个）重心为 $v$ 。结点 $v$ 是根结点时，命题显然成立。下面设 $v$ 是非根结点， $u$ 是它的父结点。因为 $∣ T_{u}^{(v)} ∣ \leq ∣ T ∣/2$ ，所以， $v$ 所在子树大小至少是 $∣ T ∣/2$ 。但是，只要它到根结点的路径上经过一次轻边，它所在子树大小将严格小于 $∣ T ∣/2$ ，矛盾。所以，它必然在根结点所在重链上。进而，根据重链的定义，根结点重子结点对应子树中根结点所在重链就是原树中根结点所在重链的一部分；而且，根据性质 3，在重子结点对应子树上添加重子结点及其所有轻子结点对应子树后，重心位置将沿着当前重心和根结点路径移动，所以新重心必然是旧重心的祖先。

求法

根据重心的等价定义，有两种方法可以在 $O (n)$ 时间内求出树的所有重心，其中， $n$ 为树的大小。

DFS 统计子树大小

通过 DFS 计算每个子树的大小。对每个结点，记录它的所有子结点对应子树的大小，并利用总结点数减去当前子树大小得到「向上」的子树的大小，然后就可以依据定义找到重心了。

参考实现

const int MAXN = 50005;
 
int n;
// 这份代码默认节点编号从 1 开始，即 i ∈ [1,n]
int siz[MAXN],  // 这个节点的「大小」（所有子树上节点数 + 该节点）
    weight[MAXN];  // 这个节点的「重量」，即所有子树「大小」的最大值
vector<int> centroids;  // 用于记录树的重心（存的是节点编号）
vector<int> g[MAXN];
 
void dfs(int cur, int fa) {  // cur 表示当前节点 (current)
  siz[cur] = 1;
  weight[cur] = 0;
  for (int v : g[cur]) {
    if (v != fa) {  // v 表示这条有向边所通向的节点
      dfs(v, cur);
      siz[cur] += siz[v];
      weight[cur] = max(weight[cur], siz[v]);
    }
  }
  weight[cur] = max(weight[cur], n - siz[cur]);
  if (weight[cur] <= n / 2) {  // 依照树的重心的定义统计
    centroids.push_back(cur);
  }
}
 
void get_centroids() { dfs(1, 0); }

换根 DP 统计深度和

还可以通过换根 DP 计算出以不同结点为根时，所有结点的深度和（即到当前根结点的距离和）。根据定义，只需要找到使得这一深度和最小的结点即可。

参考实现

const int N = 50005;
 
int n, siz[N];
long long dp[N], ans[N];
vector<int> g[N], centroids;
 
// 求 1 号节点到所有其他节点的距离和
void dfs1(int u, int fa) {
  siz[u] = 1;
  dp[u] = 0;
  for (int v : g[u]) {
    if (v == fa) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    dp[u] += dp[v] + siz[v];  // 子树节点到 u 的距离和
  }
}
 
// 通过换根 DP 求所有节点为树根时对应的距离和
void dfs2(int u, int fa) {
  for (int v : g[u]) {
    if (v == fa) continue;
    ans[v] = ans[u] - siz[v] + (n - siz[v]);
    dfs2(v, u);
  }
}
 
// 求树的重心
void get_centroids() {
  dfs1(1, 0);
  ans[1] = dp[1];
  dfs2(1, 0);
 
  long long mini = std::numeric_limits<long long>::max();
  for (int i = 1; i <= n; i++) {
    if (ans[i] < mini) {
      mini = ans[i];
      centroids = {i};
    } else if (ans[i] == mini)
      centroids.push_back(i);
  }
}

例题

Codeforces Round 359 (Div. 1) B. Kay and Snowflake

给定一棵有根树，求出每一棵子树的重心。

解题思路

根据性质 3，对于一棵以点 $u$ 为根的子树，其重心一定在所有以 $u$ 的直接子结点为根的子树的重心到点 $u$ 的路径上。

类似于上文提到的 DFS 求重心方法，对于每棵以结点 $u$ 为根的子树，先求出所有以其直接子结点为根的子树的重心（叶子结点的重心是其本身），然后向上判断路径上的结点是不是重心即可。

在 $O (n)$ 时间内可以求出所有子树的重心。

参考代码

#include <iostream>
#include <vector>
using namespace std;
 
constexpr int N = 3e5 + 5;
 
int n, q;  // 点数，询问数
int fa[N];
vector<int> son[N];
int siz[N],     // 子树大小
    ans[N],     // 以节点 u 为根的子树重心是 ans[u]
    weight[N];  // 节点重量（不包括向上的子树）
 
void dfs(int u) {
  siz[u] = 1, ans[u] = u;
  for (int v : son[u]) {
    dfs(v);
    siz[u] += siz[v];
    weight[u] = max(weight[u], siz[v]);
  }
  for (int v : son[u]) {
    int p = ans[v];
    while (p != u) {
      if (max(weight[p], siz[u] - siz[p]) <= siz[u] / 2) {
        ans[u] = p;
        break;
      } else
        p = fa[p];
    }
  }
}
 
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> q;
  for (int v = 2; v <= n; v++) cin >> fa[v], son[fa[v]].push_back(v);
  dfs(1);
  while (q--) {
    int u;
    cin >> u;
    cout << ans[u] << '\n';
  }
  return 0;
}

Sean's Blog

探索

04.树的重心

定义

性质

求法

DFS 统计子树大小

换根 DP 统计深度和

例题

习题

参考资料

目录

关系图谱

目录