Bỏ qua

Đường kính cây

Đường đi đơn dài nhất giữa hai đỉnh bất kỳ trên cây được gọi là đường kính của cây.

Kiến thức nền tảng: Cơ bản về cây.

Dẫn nhập

Rõ ràng, một cây có thể có nhiều đường kính, nhưng tất cả đều có cùng độ dài.

Có thể dùng hai lần DFS hoặc DP trên cây để tìm đường kính trong thời gian \(O(n)\).

Hai lần DFS

Bắt đầu từ một đỉnh bất kỳ \(y\), thực hiện DFS đầu tiên để tìm đỉnh xa nhất \(z\). Sau đó, từ \(z\) thực hiện DFS lần hai để tìm đỉnh xa nhất \(z'\). Khi đó, \(\delta(z, z')\) chính là đường kính của cây.

Nếu \(z\) là một đầu mút của đường kính, thì \(z'\) chắc chắn là đầu mút còn lại. Ta cần chứng minh rằng, với mọi trường hợp, \(z\) luôn là một đầu mút của đường kính.

Định lý: Trên một cây, bắt đầu từ bất kỳ đỉnh \(y\), DFS đến đỉnh xa nhất \(z\) thì \(z\) luôn là một đầu mút của đường kính.

Chứng minh

Dùng phản chứng. Gọi đỉnh xuất phát là \(y\). Giả sử đường kính thực sự là \(\delta(s, t)\), nhưng DFS từ \(y\) lại đến đỉnh xa nhất \(z\) mà \(z\) không phải \(s\) hoặc \(t\). Xét ba trường hợp:

  • Nếu \(y\) nằm trên \(\delta(s, t)\):

y 在 s-t 上

Có \(\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)\), mâu thuẫn với giả thiết \(\delta(s,t)\) là đường kính.

  • Nếu \(y\) không nằm trên \(\delta(s, t)\), và \(\delta(y,z)\) có chung đoạn với \(\delta(s,t)\):

y 不在 s-t 上，y-z 与 s-t 存在重合路径

Có \(\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)\), mâu thuẫn với giả thiết.

  • Nếu \(y\) không nằm trên \(\delta(s, t)\), và \(\delta(y,z)\) không có đoạn chung với \(\delta(s,t)\):

y 不在 s-t 上，y-z 与 s-t 不存在重合路径

Có \(\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x',z) > \delta(x',t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)\), mâu thuẫn với giả thiết.

Vậy cả ba trường hợp đều dẫn đến mâu thuẫn, định lý được chứng minh.

Cạnh có trọng số âm

Chứng minh trên chỉ đúng khi mọi cạnh đều không âm. Nếu cây có cạnh âm, không thể dùng hai lần DFS để tìm đường kính.

Nếu cần truy vết các đỉnh trên đường kính, chỉ cần lưu lại đỉnh cha trong lần DFS thứ hai, rồi lần ngược lại từ một đầu mút.

DP trên cây

Phương pháp 1

Gán gốc là \(1\), với mỗi đỉnh, lưu \(d_1\) là độ dài xích dài nhất đi xuống, \(d_2\) là xích dài nhì (không trùng cạnh với \(d_1\)). Đường kính là giá trị lớn nhất của \(d_1 + d_2\) trên toàn bộ các đỉnh.

DP trên cây có thể áp dụng cả khi có cạnh âm.

Nếu cần truy vết các đỉnh trên đường kính, khi tính \(d_1, d_2\) nên lưu lại con tương ứng, rồi lần lượt đi theo hai nhánh này.

Phương pháp 2

Có thể dùng chỉ một mảng. Đặt \(dp[u]\) là độ dài xích dài nhất từ \(u\) đi xuống. Khi duyệt các con \(v\) của \(u\), cập nhật \(dp[u] = \max(dp[u], dp[v] + w(u, v))\).

Đường kính là giá trị lớn nhất của \(dp[u] + dp[v] + w(u, v)\) trên mọi cặp \((u, v)\) cha-con.

Bài tập ví dụ

Luogu B4016 Đường kính của cây

Cho cây \(n\) đỉnh, hãy tính độ dài đường kính. \(1\leq n\leq 10^5\).

Cài đặt hai lần DFS 
 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
#include <cstdio>
#include <vector>
using namespace std;

constexpr int N = 100000 + 10;

int n, c, d[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}
Cài đặt DP trên cây với hai mảng 
 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
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

constexpr int N = 100000 + 10;

int n, d;
int d1[N], d2[N];
vector<int> E[N];

void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
      d2[u] = d1[u], d1[u] = t;
    else if (t > d2[u])
      d2[u] = t;
  }
  d = max(d, d1[u] + d2[u]);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}
Cài đặt DP trên cây với một mảng 
 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
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

constexpr int N = 100000 + 10;

int n, d;
int dp[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    d = max(d, dp[u] + dp[v] + 1);
    dp[u] = max(dp[u], dp[v] + 1);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}

Tính chất

Đường kính của cây có tính chất: nếu mọi cạnh đều có trọng số dương, thì trung điểm của mọi đường kính đều trùng nhau.

Chứng minh

Dùng phản chứng. Giả sử có hai đường kính \(\delta(s,t)\) và \(\delta(s',t')\) có trung điểm khác nhau, gọi là \(x\) và \(x'\). Rõ ràng, \(\delta(s,x) = \delta(x,t) = \delta(s',x') = \delta(x',t')\).

无负权边的树所有直径的中点重合

Có \(\delta(s,t') = \delta(s,x) + \delta(x,x') + \delta(x',t') > \delta(s,x) + \delta(x,t) = \delta(s,t)\), mâu thuẫn với giả thiết.

Bài tập

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply