跳转至

樹的重心

定義

如果在樹中選擇某個節點並刪除，這棵樹將分為若干棵子樹，統計子樹節點數並記錄最大值。取遍樹上所有節點，使此最大值取到最小的節點被稱為整個樹的重心。

（這裏以及下文中的「子樹」若無特殊説明都是指無根樹的子樹，即包括「向上」的那棵子樹，並且不包括整棵樹自身。）

性質

  • 樹的重心如果不唯一，則至多有兩個，且這兩個重心相鄰。
  • 以樹的重心為根時，所有子樹的大小都不超過整棵樹大小的一半。
  • 樹中所有點到某個點的距離和中，到重心的距離和是最小的；如果有兩個重心，那麼到它們的距離和一樣。
  • 把兩棵樹通過一條邊相連得到一棵新的樹，那麼新的樹的重心在連接原來兩棵樹的重心的路徑上。
  • 在一棵樹上添加或刪除一個葉子，那麼它的重心最多隻移動一條邊的距離。

求法

在 DFS 中計算每個子樹的大小，記錄「向下」的子樹的最大大小，利用總點數 - 當前子樹（這裏的子樹指有根樹的子樹）的大小得到「向上」的子樹的大小，然後就可以依據定義找到重心了。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 這份代碼默認節點編號從 1 開始，即 i ∈ [1,n]
int size[MAXN],  // 這個節點的「大小」（所有子樹上節點數 + 該節點）
    weight[MAXN],  // 這個節點的「重量」，即所有子樹「大小」的最大值
    centroid[2];  // 用於記錄樹的重心（存的是節點編號）

void GetCentroid(int cur, int fa) {  // cur 表示當前節點 (current)
  size[cur] = 1;
  weight[cur] = 0;
  for (int i = head[cur]; i != -1; i = e[i].nxt) {
    if (e[i].to != fa) {  // e[i].to 表示這條有向邊所通向的節點。
      GetCentroid(e[i].to, cur);
      size[cur] += size[e[i].to];
      weight[cur] = max(weight[cur], size[e[i].to]);
    }
  }
  weight[cur] = max(weight[cur], n - size[cur]);
  if (weight[cur] <= n / 2) {  // 依照樹的重心的定義統計
    centroid[centroid[0] != 0] = cur;
  }
}

例題

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

給定一棵有根樹，求出每一棵子樹（有根樹意義下且包含整顆樹本身）的重心是哪一個節點。

解題思路

本題中子樹無特殊説明指的是有根樹意義下且包含整顆樹本身的「向下」的子樹。

根據第四條性質，對於一棵以點 \(u\) 為根的子樹，其重心一定在所有以 \(u\) 的直接子節點為根的子樹的重心到點 \(u\) 的路徑上。

類似於上文提到的 DFS 求重心方法，對於每棵以節點 \(u\) 為根的子樹，先求出所有以其直接子節點為根的子樹的重心（葉子節點的重心是其本身），然後向上判斷路徑上的節點是不是重心即可。

時間複雜度為 \(O(n)\) 可以求出所有子樹的重心。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

const 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];
    }
  }
}

signed main() {
  ios::sync_with_stdio(0);
  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;
}

參考

http://fanhq666.blog.163.com/blog/static/81943426201172472943638/(博客園轉載，Internet Archive)

https://blog.csdn.net/weixin_43810158/article/details/88391828

https://www.cnblogs.com/zinthos/p/3899075.html

https://www.cnblogs.com/suxxsfe/p/13543253.html

《信息學奧林匹克辭典》2.4.7.11 章 1. 樹的重心

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, Marcythm, LucienShui, Anguei, H-J-Granger, CornWorld, ttzc
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用