Bỏ qua

LCA

Định nghĩa

Tổ tiên chung gần nhất, viết tắt là LCA (Lowest Common Ancestor). Với hai đỉnh bất kỳ, tổ tiên chung gần nhất là tổ tiên chung nằm xa gốc nhất (gần hai đỉnh nhất). Để thuận tiện, ta ký hiệu tổ tiên chung gần nhất của tập \(S=\{v_1,v_2,\ldots,v_n\}\) là \(\text{LCA}(v_1,v_2,\ldots,v_n)\) hoặc \(\text{LCA}(S)\).

Tính chất

Phần tính chất này được dịch và chỉnh sửa từ wcipeg.

  1. \(\text{LCA}(\{u\})=u\);
  2. \(u\) là tổ tiên của \(v\) khi và chỉ khi \(\text{LCA}(u,v)=u\);
  3. Nếu \(u\) không là tổ tiên của \(v\) và \(v\) không là tổ tiên của \(u\), thì \(u,v\) nằm ở hai cây con khác nhau của \(\text{LCA}(u,v)\);
  4. Trong phép duyệt tiền thứ tự, \(\text{LCA}(S)\) xuất hiện trước tất cả các phần tử của \(S\); trong phép duyệt hậu thứ tự, \(\text{LCA}(S)\) xuất hiện sau tất cả các phần tử của \(S\);
  5. Tổ tiên chung gần nhất của hợp hai tập là tổ tiên chung gần nhất của hai tổ tiên chung gần nhất của từng tập, tức là \(\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))\);
  6. Tổ tiên chung gần nhất của hai đỉnh luôn nằm trên đường đi ngắn nhất giữa hai đỉnh đó trên cây;
  7. \(d(u,v)=h(u)+h(v)-2h(\text{LCA}(u,v))\), trong đó \(d\) là khoảng cách giữa hai đỉnh trên cây, \(h\) là khoảng cách từ đỉnh đến gốc.

Các phương pháp tìm LCA

Thuật toán đơn giản

Quy trình

Có thể mỗi lần chọn đỉnh có độ sâu lớn hơn để nhảy lên trên. Rõ ràng trên cây, hai đỉnh cuối cùng sẽ gặp nhau, vị trí gặp chính là LCA cần tìm. Hoặc có thể đưa hai đỉnh về cùng độ sâu trước, sau đó cùng nhảy lên, cuối cùng cũng sẽ gặp nhau.

Độ phức tạp

Thuật toán đơn giản cần duyệt DFS toàn bộ cây để tiền xử lý, độ phức tạp \(O(n)\), mỗi truy vấn mất \(\Theta(n)\). Nếu cây có tính chất ngẫu nhiên, độ phức tạp phụ thuộc vào chiều cao kỳ vọng của cây.

Thuật toán nhảy bậc (Binary Lifting)

Quy trình

Thuật toán nhảy bậc là phương pháp kinh điển nhất để tìm LCA, cải tiến từ thuật toán đơn giản. Bằng cách tiền xử lý mảng \(\text{fa}_{x,i}\), con trỏ có thể nhảy xa hơn, giảm mạnh số lần nhảy. \(\text{fa}_{x,i}\) là tổ tiên thứ \(2^i\) của đỉnh \(x\). Mảng này có thể tính bằng DFS.

Cách tối ưu hóa: Ở giai đoạn đầu, cần đưa \(u,v\) về cùng độ sâu. Tính hiệu độ sâu \(y\), phân tích nhị phân \(y\) để thực hiện số lần nhảy bằng số bit 1 trong \(y\). Giai đoạn hai, từ \(i\) lớn nhất về \(0\), nếu \(\text{fa}_{u,i}\not=\text{fa}_{v,i}\) thì cập nhật \(u\gets\text{fa}_{u,i},v\gets\text{fa}_{v,i}\). Cuối cùng, LCA là \(\text{fa}_{u,0}\).

Độ phức tạp

Tiền xử lý \(O(n \log n)\), mỗi truy vấn \(O(\log n)\). Có thể đổi thứ tự hai chiều của mảng fa để tối ưu cache.

Ví dụ

HDU 2586 How far away? - Truy vấn đường đi ngắn nhất trên cây.

Có thể tìm LCA trước rồi dùng tính chất 7 để trả lời, hoặc tính luôn khi tìm LCA.

Mã mẫu 
 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstring>
#include <iostream>
#include <vector>

constexpr int MXN = 40005;
using namespace std;
vector<int> v[MXN];
vector<int> w[MXN];

int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;

// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {
  // 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
  // 2^(i-1) 的祖先节点。
  for (int i = 1; i < 31; ++i) {
    fa[root][i] = fa[fa[root][i - 1]][i - 1];
    cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
  }
  // 遍历子节点来进行 dfs。
  int sz = v[root].size();
  for (int i = 0; i < sz; ++i) {
    if (v[root][i] == fno) continue;
    cost[v[root][i]][0] = w[root][i];
    dfs(v[root][i], root);
  }
}

// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {
  // 令 y 比 x 深。
  if (dep[x] > dep[y]) swap(x, y);
  // 令 y 和 x 在一个深度。
  int tmp = dep[y] - dep[x], ans = 0;
  for (int j = 0; tmp; ++j, tmp >>= 1)
    if (tmp & 1) ans += cost[y][j], y = fa[y][j];
  // 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
  if (y == x) return ans;
  // 不然的话，找到第一个不是它们祖先的两个点。
  for (int j = 30; j >= 0 && y != x; --j) {
    if (fa[x][j] != fa[y][j]) {
      ans += cost[x][j] + cost[y][j];
      x = fa[x][j];
      y = fa[y][j];
    }
  }
  // 返回结果。
  ans += cost[x][0] + cost[y][0];
  return ans;
}

void Solve() {
  cin.tie(nullptr)->sync_with_stdio(false);
  // 初始化表示祖先的数组 fa，代价 cost 和深度 dep。
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  // 读入树：节点数一共有 n 个，查询 m 次，每一次查找两个节点的 lca 点。
  cin >> n >> m;
  // 初始化树边和边权
  for (int i = 1; i <= n; ++i) {
    v[i].clear();
    w[i].clear();
  }
  for (int i = 1; i < n; ++i) {
    cin >> a >> b >> c;
    v[a].push_back(b);
    v[b].push_back(a);
    w[a].push_back(c);
    w[b].push_back(c);
  }
  // 为了计算 lca 而使用 dfs。
  dfs(1, 0);
  for (int i = 0; i < m; ++i) {
    cin >> a >> b;
    cout << lca(a, b) << '\n';
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) Solve();
  return 0;
}

Thuật toán Tarjan

Quy trình

Thuật toán Tarjan là thuật toán offline, cần dùng DSU - cấu trúc hợp nhất-tìm đại diện để lưu tổ tiên của mỗi đỉnh. Cách làm:

  1. Nhập các cạnh (dạng danh sách kề), các truy vấn (lưu ở một danh sách kề khác). Mỗi truy vấn thêm cả hai chiều vào mảng queryEdge.
  2. Thực hiện DFS, dùng mảng visited để đánh dấu đã thăm, parent lưu cha hiện tại.
  3. Áp dụng tư duy quay lui: khi duyệt đến một đỉnh, coi nó là gốc của chính nó. Sau khi DFS xong toàn bộ cây con, cập nhật gốc của nó là cha của nó.
  4. Khi quay lui, nếu truy vấn xuất phát từ đỉnh này và đỉnh còn lại đã được thăm, cập nhật kết quả LCA.
  5. In kết quả.

Độ phức tạp

Cần khởi tạo DSU, tiền xử lý \(O(n)\).

Thuật toán Tarjan cơ bản xử lý \(m\) truy vấn trong \(O(m \alpha(m+n, n) + n)\), nhưng hằng số lớn hơn thuật toán nhảy bậc. Có thể đạt \(O(m+n)\).

Chú ý

Không có chuyện “DSU trong Tarjan LCA có truy vấn find() \(O(1)\)”. Thuật toán Tarjan cơ bản có độ phức tạp \(O(m \alpha(m+n, n) + n)\). Nếu muốn tuyến tính nghiêm ngặt, xem bài báo của Gabow và Tarjan 1983 với cách \(O(m+n)\).

Mã mẫu

Mã mẫu 
 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

class Edge {
 public:
  int toVertex, fromVertex;
  int next;
  int LCA;
  Edge() : toVertex(-1), fromVertex(-1), next(-1), LCA(-1) {};
  Edge(int u, int v, int n) : fromVertex(u), toVertex(v), next(n), LCA(-1) {};
};

constexpr int MAX = 100;
int head[MAX], queryHead[MAX];
Edge edge[MAX], queryEdge[MAX];
int parent[MAX], visited[MAX];
int vertexCount, queryCount;

int find(int x) {
  if (parent[x] == x) {
    return x;
  } else {
    return parent[x] = find(parent[x]);
  }
}

void tarjan(int u) {
  parent[u] = u;
  visited[u] = 1;

  for (int i = head[u]; i != -1; i = edge[i].next) {
    Edge& e = edge[i];
    if (!visited[e.toVertex]) {
      tarjan(e.toVertex);
      parent[e.toVertex] = u;
    }
  }

  for (int i = queryHead[u]; i != -1; i = queryEdge[i].next) {
    Edge& e = queryEdge[i];
    if (visited[e.toVertex]) {
      queryEdge[i ^ 1].LCA = e.LCA = find(e.toVertex);
    }
  }
}

int main() {
  memset(head, 0xff, sizeof(head));
  memset(queryHead, 0xff, sizeof(queryHead));

  cin >> vertexCount >> queryCount;
  int count = 0;
  for (int i = 0; i < vertexCount - 1; i++) {
    int start = 0, end = 0;
    cin >> start >> end;

    edge[count] = Edge(start, end, head[start]);
    head[start] = count;
    count++;

    edge[count] = Edge(end, start, head[end]);
    head[end] = count;
    count++;
  }

  count = 0;
  for (int i = 0; i < queryCount; i++) {
    int start = 0, end = 0;
    cin >> start >> end;

    queryEdge[count] = Edge(start, end, queryHead[start]);
    queryHead[start] = count;
    count++;

    queryEdge[count] = Edge(end, start, queryHead[end]);
    queryHead[end] = count;
    count++;
  }

  tarjan(1);

  for (int i = 0; i < queryCount; i++) {
    Edge& e = queryEdge[i * 2];
    cout << "(" << e.fromVertex << "," << e.toVertex << ") " << e.LCA << endl;
  }

  return 0;
}

Dùng Euler Tour chuyển về bài toán RMQ

Định nghĩa

Duyệt DFS cây, mỗi lần đến một đỉnh (kể cả khi quay lui) đều ghi lại chỉ số, thu được một dãy độ dài \(2n-1\), gọi là Euler Tour của cây.

Ký hiệu vị trí xuất hiện đầu tiên của \(u\) trong Euler Tour là \(pos(u)\) (Euler index), dãy Euler Tour là \(E[1..2n-1]\).

Quy trình

Có Euler Tour, bài toán LCA chuyển thành bài toán RMQ trong thời gian tuyến tính: \(pos(LCA(u, v))=\min\{pos(k)|k\in E[pos(u)..pos(v)]\}\).

Giải thích: từ \(u\) đến \(v\) luôn đi qua \(LCA(u,v)\), nhưng không đi qua tổ tiên của \(LCA(u,v)\). Do đó, trong đoạn từ \(u\) đến \(v\) trên Euler Tour, đỉnh có chỉ số nhỏ nhất chính là \(LCA(u,v)\).

DFS tính Euler Tour \(O(n)\), độ dài dãy cũng \(O(n)\), nên chuyển bài toán LCA về RMQ cùng kích thước trong \(O(n)\).

Mã mẫu

Mã mẫu 
 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
int dfn[N << 1], pos[N], tot, st[30][(N << 1) + 2],
    rev[30][(N << 1) + 2];  // rev biểu diễn chỉ số đỉnh ứng với độ sâu nhỏ nhất

void dfs(int cur, int dep) {
  dfn[++tot] = cur;
  depth[tot] = dep;
  pos[cur] = tot;
  for (int i = head[t]; i; i = side[i].next) {
    int v = side[i].to;
    if (!pos[v]) {
      dfs(v, dep + 1);
      dfn[++tot] = cur, depth[tot] = dep;
    }
  }
}

void init() {
  for (int i = 2; i <= tot + 1; ++i)
    lg[i] = lg[i >> 1] + 1;  // Tiền xử lý log2 để tối ưu hằng số
  for (int i = 1; i <= tot; i++) st[0][i] = depth[i], rev[0][i] = dfn[i];
  for (int i = 1; i <= lg[tot]; i++)
    for (int j = 1; j + (1 << i) - 1 <= tot; j++)
      if (st[i - 1][j] < st[i - 1][j + (1 << i - 1)])
        st[i][j] = st[i - 1][j], rev[i][j] = rev[i - 1][j];
      else
        st[i][j] = st[i - 1][j + (1 << i - 1)],
        rev[i][j] = rev[i - 1][j + (1 << i - 1)];
}

int query(int l, int r) {
  int k = lg[r - l + 1];
  return st[k][l] < st[k][r + 1 - (1 << k)] ? rev[k][l]
                                            : rev[k][r + 1 - (1 << k)];
}

Khi cần truy vấn LCA của \((u, v)\), chỉ cần truy vấn đoạn \([\min\{pos[u], pos[v]\}, \max\{pos[u], pos[v]\}]\) để lấy đỉnh có độ sâu nhỏ nhất.

Nếu dùng Sparse Table để giải RMQ, thuật toán không hỗ trợ cập nhật online, tiền xử lý \(O(n\log n)\), mỗi truy vấn LCA \(O(1)\).

Heavy-Light Decomposition (HLD)

LCA là đỉnh có độ sâu nhỏ hơn khi hai con trỏ cùng nhảy lên một heavy chain.

Tiền xử lý \(O(n)\), mỗi truy vấn \(O(\log n)\), hằng số nhỏ.

Trong Link Cut Tree, nếu thực hiện hai thao tác access liên tiếp với hai đỉnh u và v, thì kết quả trả về của lần thứ hai chính là LCA của u và v.

Nếu không có thao tác link/cut, mỗi truy vấn LCA bằng Link Cut Tree mất \(O(\log n)\).

Chuẩn RMQ

Như đã nói, chuyển LCA về RMQ, điểm nghẽn là RMQ. Nếu giải RMQ trong \(O(n)\sim O(1)\) thì LCA cũng vậy.

Chú ý Euler Tour có tính chất: hiệu hai phần tử liên tiếp là \(1\) hoặc \(-1\), nên có thể dùng RMQ cộng/trừ 1 để giải trong \(O(n)\sim O(1)\).

Độ phức tạp \(O(n)\sim O(1)\), bộ nhớ \(O(n)\), hỗ trợ truy vấn online, hằng số lớn.

Ví dụ Luogu P3379【Mẫu】LCA

Mã mẫu 
  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
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

constexpr int N = 5e5 + 5;

struct PlusMinusOneRMQ {  // RMQ
  // Copyright (C) 2018 Skqliao. All rights served.
  constexpr static int M = 9;

  int blocklen, block, Minv[N], F[N / M * 2 + 5][M << 1], T[N], f[1 << M][M][M],
      S[N];

  void init(int n) {  // 初始化
    blocklen = std::max(1, (int)(log(n * 1.0) / log(2.0)) / 2);
    block = n / blocklen + (n % blocklen > 0);
    int total = 1 << (blocklen - 1);
    for (int i = 0; i < total; i++) {
      for (int l = 0; l < blocklen; l++) {
        f[i][l][l] = l;
        int now = 0, minv = 0;
        for (int r = l + 1; r < blocklen; r++) {
          f[i][l][r] = f[i][l][r - 1];
          if ((1 << (r - 1)) & i) {
            now++;
          } else {
            now--;
            if (now < minv) {
              minv = now;
              f[i][l][r] = r;
            }
          }
        }
      }
    }
    T[1] = 0;
    for (int i = 2; i < N; i++) {
      T[i] = T[i - 1];
      if (!(i & (i - 1))) {
        T[i]++;
      }
    }
  }

  void initmin(int a[], int n) {
    for (int i = 0; i < n; i++) {
      if (i % blocklen == 0) {
        Minv[i / blocklen] = i;
        S[i / blocklen] = 0;
      } else {
        if (a[i] < a[Minv[i / blocklen]]) {
          Minv[i / blocklen] = i;
        }
        if (a[i] > a[i - 1]) {
          S[i / blocklen] |= 1 << (i % blocklen - 1);
        }
      }
    }
    for (int i = 0; i < block; i++) {
      F[i][0] = Minv[i];
    }
    for (int j = 1; (1 << j) <= block; j++) {
      for (int i = 0; i + (1 << j) - 1 < block; i++) {
        int b1 = F[i][j - 1], b2 = F[i + (1 << (j - 1))][j - 1];
        F[i][j] = a[b1] < a[b2] ? b1 : b2;
      }
    }
  }

  int querymin(int a[], int L, int R) {
    int idl = L / blocklen, idr = R / blocklen;
    if (idl == idr)
      return idl * blocklen + f[S[idl]][L % blocklen][R % blocklen];
    else {
      int b1 = idl * blocklen + f[S[idl]][L % blocklen][blocklen - 1];
      int b2 = idr * blocklen + f[S[idr]][0][R % blocklen];
      int buf = a[b1] < a[b2] ? b1 : b2;
      int c = T[idr - idl - 1];
      if (idr - idl - 1) {
        int b1 = F[idl + 1][c];
        int b2 = F[idr - 1 - (1 << c) + 1][c];
        int b = a[b1] < a[b2] ? b1 : b2;
        return a[buf] < a[b] ? buf : b;
      }
      return buf;
    }
  }
} rmq;

int n, m, s;

struct Edge {
  int v, nxt;
} e[N * 2];

int tot, head[N];

void init(int n) {
  tot = 0;
  fill(head, head + n + 1, 0);
}

void addedge(int u, int v) {  // 加边
  ++tot;
  e[tot] = Edge{v, head[u]};
  head[u] = tot;

  ++tot;
  e[tot] = Edge{u, head[v]};
  head[v] = tot;
}

int dfs_clock, dfn[N * 2], dep[N * 2], st[N];

void dfs(int u, int fa, int d) {
  st[u] = dfs_clock;

  dfn[dfs_clock] = u;
  dep[dfs_clock] = d;
  ++dfs_clock;

  int v;
  for (int i = head[u]; i; i = e[i].nxt) {
    v = e[i].v;
    if (v == fa) continue;
    dfs(v, u, d + 1);
    dfn[dfs_clock] = u;
    dep[dfs_clock] = d;
    ++dfs_clock;
  }
}

void build_lca() {  // like init
  rmq.init(dfs_clock);
  rmq.initmin(dep, dfs_clock);
}

int LCA(int u, int v) {  // 求解LCA，看题解用RMQ的方法
  int l = st[u], r = st[v];
  if (l > r) swap(l, r);
  return dfn[rmq.querymin(dep, l, r)];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> s;

  init(n);
  int u, v;
  for (int i = 1; i <= n - 1; ++i) {
    cin >> u >> v;
    addedge(u, v);
  }

  dfs_clock = 0;
  dfs(s, s, 0);

  build_lca();

  for (int i = 1; i <= m; ++i) {
    cin >> u >> v;
    cout << LCA(u, v) << '\n';
  }

  return 0;
}

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:ouuan, Backl1ght, billchenchina, CCXXXI, ChickenHu, ChungZH, cjsoft, countercurrent-time, diauweb, Early0v0, Enter-tainer, EtaoinWu, H-J-Granger, H-Shen, Henry-ZHR, HeRaNO, hsfzLZH1, huaruoji, iamtwz, imp2002, Ir1d, kenlig, Konano, Lyccrius, Marcythm, Menci, NachtgeistW, PeterlitsZo, psz2007, shuzhouliu, SkqLiao, sshwy, SukkaW, therehello, TrisolarisHD, ttzztztz, vincent-163, WAAutoMaton, Hunter19019
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply