Bỏ qua

Trọng tâm cây

Bài viết này giới thiệu khái niệm trọng tâm của cây (centroid) và các tính chất cơ bản.

Định nghĩa

Trong cây \(T\), nếu xóa một đỉnh \(v\), mọi thành phần liên thông còn lại đều có kích thước không vượt quá một nửa số đỉnh của cây ban đầu, thì \(v\) được gọi là trọng tâm (centroid) của cây. Kích thước thành phần liên thông lớn nhất sau khi xóa \(v\) còn gọi là trọng lượng (weight) của đỉnh đó. Như vậy, trọng tâm là đỉnh có trọng lượng không vượt quá một nửa số đỉnh của cây.

“Cây con”

Bài viết này có thể đề cập cả cây vô gốc, cây có gốc, và trường hợp đổi gốc cây. Để tránh nhầm lẫn, ký hiệu \(T\) là cây vô gốc, \(T^{(v)}\) là cây có gốc tại \(v\). “Cây con” ở đây luôn là cây con trong cây có gốc: tức là một đỉnh và toàn bộ hậu duệ của nó. Cây con gốc \(u\) trong \(T^{(v)}\) ký hiệu là \(T^{(v)}_u\). Định nghĩa này bao gồm cả toàn bộ cây. Nếu muốn loại trừ toàn bộ cây, sẽ gọi là “cây con thực sự”.

Trong cây vô gốc, “cây con” thường chỉ thành phần liên thông. Khi nói về trọng tâm, một số tài liệu dùng “cây con” để chỉ thành phần liên thông lớn nhất sau khi xóa một đỉnh, hoặc thành phần thu được khi xóa một cạnh. Hai cách này đều cho cùng tập hợp cây con, và không bao gồm toàn bộ cây. Vì vậy, bài viết này sẽ tránh dùng “cây con” cho cây vô gốc.

Khi giải bài toán trọng tâm, thường mặc định có một gốc. Khi xóa một đỉnh \(v\), ngoài các cây con của các con \(v\), còn có một “cây con hướng lên” (tức là phần còn lại của cây). Nếu \(v\) có cha là \(u\), thì cây con hướng lên là \(T_u^{(v)}\). Khi đề cập đến loại cây con này, bài viết sẽ nói rõ là “cây con hướng lên”. Nếu không nói gì, “cây con” không bao gồm phần này.

Lưu ý, các thành phần liên thông sau khi xóa trọng tâm cũng là cây vô gốc. Khi xóa trọng tâm, cây sẽ tách thành nhiều cây nhỏ, mỗi cây có kích thước không quá một nửa cây gốc. Tính chất này rất hữu ích cho các bài toán chia để trị trên cây, như phân chia theo trọng tâm.

Tính chất

Phần này bàn về các tính chất của trọng tâm. Trước hết, trọng tâm có các định nghĩa tương đương sau:

Định nghĩa tương đương

Đỉnh \(v\) là trọng tâm của cây \(T\) khi và chỉ khi thỏa mãn một trong các điều kiện sau:

  1. Xóa \(v\), mọi thành phần liên thông còn lại đều có kích thước không vượt quá một nửa số đỉnh cây.
  2. Trong tất cả các đỉnh, xóa đỉnh nào thì thành phần lớn nhất còn lại là nhỏ nhất; \(v\) là đỉnh đạt giá trị nhỏ nhất này.
  3. Tổng khoảng cách từ \(v\) đến mọi đỉnh khác là nhỏ nhất.
  1. Khi lấy \(v\) làm gốc, mọi cây con thực sự đều có kích thước không vượt quá một nửa số đỉnh cây.
  2. Trong tất cả các gốc, gốc nào có cây con lớn nhất nhỏ nhất thì đó là trọng tâm.
  3. Tổng độ sâu các đỉnh nhỏ nhất khi lấy \(v\) làm gốc.
Chứng minh

...existing code...

Ngoài các định nghĩa trên, trọng tâm còn có các tính chất sau:

Tính chất
  1. Nếu trọng tâm không duy nhất thì có đúng hai đỉnh, và hai đỉnh này kề nhau. Nếu xóa cạnh nối hai trọng tâm, cây tách thành hai phần bằng nhau.
  2. Khi thêm hoặc xóa một lá, trọng tâm chỉ dịch chuyển tối đa một cạnh.
  3. Khi nối hai cây bằng một cạnh, trọng tâm của cây mới nằm trên đường nối hai trọng tâm cũ.
  4. Trọng tâm của cây có gốc luôn nằm trên heavy path của gốc. Trọng tâm của cây là tổ tiên của trọng tâm các cây con nặng nhất của gốc.
Chứng minh

...existing code...

Cách tìm trọng tâm

Dựa vào các định nghĩa tương đương, có hai cách tìm trọng tâm cây trong \(O(n)\) với \(n\) là số đỉnh.

DFS tính kích thước cây con

Dùng DFS tính kích thước mỗi cây con. Với mỗi đỉnh, lưu kích thước các cây con, và phần còn lại (cây con hướng lên) bằng tổng số đỉnh trừ kích thước cây con hiện tại. Từ đó xác định trọng tâm.

Cài đặt tham khảo 
 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
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 đổi gốc tính tổng độ sâu

Có thể dùng DP đổi gốc để tính tổng độ sâu các đỉnh khi lấy từng đỉnh làm gốc. Đỉnh nào có tổng nhỏ nhất là trọng tâm.

Cài đặt tham khảo 
 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
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);
  }
}

Bài tập ví dụ

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

Cho một cây có gốc, hãy tìm trọng tâm của mỗi cây con.

Hướng dẫn giải

Theo tính chất 3, trọng tâm của cây con gốc \(u\) luôn nằm trên đường nối trọng tâm các cây con trực tiếp của \(u\) với \(u\).

Tương tự cách DFS tìm trọng tâm, với mỗi cây con gốc \(u\), trước tiên tìm trọng tâm các cây con trực tiếp (lá thì trọng tâm là chính nó), sau đó kiểm tra các đỉnh trên đường lên \(u\) để xác định trọng tâm.

Có thể tìm trọng tâm mọi cây con trong \(O(n)\).

Code tham khảo 
 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
44
#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;
}

Bài tập

Tài liệu tham khảo

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Ir1d, Marcythm, LucienShui, Anguei, H-J-Granger, CornWorld, ttzc
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply