¶ Lowest Common Ancestor (LCA) - Binary Lifting
Tác giả:
- Lê Minh Hoàng - Phổ thông Năng khiếu, ĐHQG-HCM
Reviewer:
- Trần Quang Lộc - ITMO University
- Hồ Ngọc Vĩnh Phát - Đại học Khoa học Tự nhiên, ĐHQG-HCM
- Nguyễn Phú Bình - THPT Chuyên Hùng Vương, Bình Dương
- Trần Xuân Bách - THPT Chuyên Khoa học Tự nhiên, ĐHQGHN
¶ Giới thiệu
Bài toán tìm tổ tiên chung gần nhất (Lowest Common Ancestor - LCA) là một dạng bài quen thuộc thường gặp trong các cuộc thi lập trình thi đấu.
Bài toán tìm LCA có nhiều cách giải:
- Binary Lifting (Sparse Table): tiền xử lý, mỗi truy vấn.
- Euler Tour + RMQ (Segment tree): tiền xử lý, mỗi truy vấn.
- Euler Tour + RMQ (Sparse Table): tiền xử lý, mỗi truy vấn.
Trong bài viết này, ta tập trung vào cách đầu tiên là sử dụng kỹ thuật Binary Lifting để tìm LCA.
Lưu ý: Trong suốt bài viết mình dùng __lg(x) để tính của 1 số vì ta cần giá trị nguyên, còn log2(x) thì trả về số thực. Nếu không muốn dùng hàm thì có thể tính trước như sau:
int lg2[N];
void preprocess() {
lg2[1] = 0;
for (int i = 2; i < N; ++i)
lg2[i] = lg2[i / 2] + 1;
}
¶ Bài toán
Cho một cây gồm đỉnh có gốc tại đỉnh . Có truy vấn, mỗi truy vấn gồm cặp số và ta cần tìm LCA của và , tức là tìm một đỉnh xa gốc nhất nằm trên đường đi từ và đến gốc. Đặc biệt, nếu là tổ tiên của , thì là LCA của và .
Giới hạn:
¶ Ngây thơ
- Đặt là độ cao của đỉnh (độ cao của đỉnh được định nghĩa bằng khoảng cách từ đỉnh đó đến gốc của cây). Ví dụ:
- Để trả lời truy vấn , không mất tính tổng quát, giả sử :
- Bước 1: lặp lại thao tác cho nhảy lên cha của đến khi .
- Bước 2: lặp lại thao tác cho và nhảy lên cha của chúng đến khi và trùng nhau (đỉnh đó là LCA của và ban đầu).
Ví dụ:
- Ta cần tìm LCA của và . Ban đầu .
- Ta lặp lại thao tác cho nhảy lên cha của đến khi :
- dừng thao tác vì
- Sau đó, ta cho và nhảy lên cha của chúng và lặp lại thao tác đến khi đỉnh này trùng nhau:
- dừng thao tác vì và trùng nhau ()
vector<int> g[N]; // g[u]: tập các đỉnh kề với u
int par[N]; // par[u] = p nếu cha của u là p
int h[N];
void dfs(int u) {
for (int v : g[u]) {
if (v == par[u]) continue;
h[v] = h[u] + 1;
par[v] = u;
dfs(v);
}
}
int lca(int u, int v) {
// Không mất tính tổng quát, xét h[u] >= h[v]
if (h[u] < h[v]) swap(u, v);
// cho u nhảy lên cha đến khi h[u] = h[v]
while (h[u] > h[v])
u = par[u];
// cho u và v nhảy lên cha đến khi u trùng v
while (u != v) {
u = par[u];
v = par[v];
}
return u;
}
¶ Phân tích:
- Độ phức tạp tiền xử lý: (tạo mảng )
- Độ phức tạp khi truy vấn: (độ cao tối đa của 1 đỉnh là nên số bước nhảy tối đa là )
- Có truy vấn, vì thế tổng độ phức tạp là
Đối chiếu giới hạn, cách "ngây thơ" trên tỏ ra chậm chạp, không đủ để xử lí yêu cầu bài toán.
¶ Binary Lifting (nâng nhị phân)
Đầu tiên, ta sẽ tìm hiểu về ý tưởng của Binary Lifting qua bài toán con của .
¶ Bài toán 1
Cho một cây gồm đỉnh có gốc tại đỉnh . Có truy vấn, mỗi truy vấn gồm cặp số , ta cần in ra tổ tiên thứ của (tổ tiên thứ của là ).
Giới hạn:
¶ Thuật toán ngây thơ
Ta lặp lại câu lệnh u = par[u] trong k lần.
int par[N];
int ancestor_k(int u, int k) {
while (k >= 1) {
u = par[u];
--k;
}
return u;
}
¶ Phân tích:
- Độ phức tạp tiền xử lý: (tạo mảng )
- Độ phức tạp truy vấn:
- Có truy vấn, vì thế tổng độ phức tạp là
Câu hỏi đặt ra là ta còn có thể tối ưu thời gian truy vấn được hay không?
- Nhận xét: Thay vì nhảy từng bước nhỏ độ dài , ta có thể nhảy các bước lớn độ dài . Từ đó, ta có thể giảm thời gian truy vấn xuống còn
¶ Thuật toán tối ưu 1.1
- Ta xây dựng mảng là tổ tiên thứ của mỗi đỉnh.
- Khi truy vấn, ta nhảy các bước độ dài trước, sau đó kiểm tra xem có hay không (vì mod dư hoặc ).
int par[N], up2[N];
void preprocess() {
for (int u = 1; u <= n; ++u)
up2[u] = par[par[u]];
}
int ancestor_k(int u, int k) {
while (k >= 2) {
u = up2[u];
k -= 2;
}
if (k >= 1) {
u = par[u];
--k;
}
return u;
}
¶ Phân tích:
- Độ phức tạp tiền xử lý: (tạo mảng và )
- Độ phức tạp truy vấn: (1 vòng while và 1 lệnh if)
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ: (2 mảng và )
¶ Thuật toán tối ưu 1.2
Ta còn có thể tối ưu thời gian truy vấn được hay không?
- Nhận xét: Thay vì nhảy từng bước nhỏ độ dài , ta có thể nhảy các bước lớn độ dài . Từ đó, ta có thể giảm thời gian truy vấn xuống còn .
int par[N], up2[N], up4[N];
void preprocess() {
for (int u = 1; u <= n; ++u) up2[u] = par[par[u]];
for (int u = 1; u <= n; ++u) up4[u] = up2[up2[u]];
}
int ancestor_k(int u, int k) {
while (k >= 4) u = up4[u], k -= 4;
if (k >= 2) u = up2[u], k -= 2;
if (k >= 1) u = par[u], --k;
return u;
}
¶ Phân tích:
- Độ phức tạp tiền xử lý: (tạo mảng , và )
- Độ phức tạp truy vấn: (1 vòng while và 2 lệnh if)
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ: (3 mảng , và )
¶ Thuật toán tối ưu 1.3
Ta vẫn có thể tối ưu thời gian truy vấn bằng cách nhảy các bước lớn hơn (độ dài ).
int par[N], up2[N], up4[N], up8[N];
void preprocess() {
for (int u = 1; u <= n; ++u) up2[u] = par[par[u]];
for (int u = 1; u <= n; ++u) up4[u] = up2[up2[u]];
for (int u = 1; u <= n; ++u) up8[u] = up4[up4[u]];
}
int ancestor_k(int u, int k) {
while (k >= 8) u = up8[u], k -= 8;
if (k >= 4) u = up4[u], k -= 4;
if (k >= 2) u = up2[u], k -= 2;
if (k >= 1) u = par[u], --k;
return u;
}
¶ Phân tích:
- Độ phức tạp tiền xử lý: (tạo mảng , , và )
- Độ phức tạp truy vấn: (1 vòng while và 3 lệnh if)
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp tiền xử lý: (4 mảng , , và )
¶ Thuật toán tối ưu 2
Nếu ta làm tiếp như thuật toán tối ưu (tiếp tục tạo các mảng ) ta sẽ có mảng up, độ phức tạp bài toán lúc này như sau:
- Độ phức tạp tiền xử lý: (mảng và mảng )
- Độ phức tạp truy vấn: (1 vòng while và lệnh if)
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ: (mảng và mảng )
Nhưng nếu dùng mảng sẽ mang đến cho ta nhiều bất tiện (code dài, dễ sai,...). Do đó, ta có thể đặt:
- là tổ tiên thứ của (tương ứng ).
- Cha của là tổ tiên thứ (đầu tiên) của .
- Đặt là tổ tiên thứ của , ta có, tổ tiên thứ của là tổ tiên thứ của (vì )
- Cha của là tổ tiên thứ (đầu tiên) của .
- Ta có công thức truy hồi sau:
int par[N], up[N][17];
void preprocess() {
for (int u = 1; u <= n; ++u) up[u][0] = par[u];
for (int j = 1; j < 17; ++j)
for (int u = 1; u <= n; ++u)
up[u][j] = up[up[u][j - 1]][j - 1];
}
int ancestor_k(int u, int k) {
for (int j = 16; j >= 0; --j)
if (k >= (1 << j)) u = up[u][j], k -= 1 << j;
return u;
}
¶ Thuật toán tối ưu 3
Nhận xét: Ta luôn có thể tách một số nguyên dương thành tổng các lũy thừa phân biệt của 2 (hệ nhị phân). Ví dụ: .
Từ nhận xét trên, ta có một cách khác để nhảy lên tổ tiên thứ của là duyệt từ đến , nếu bit thứ của là thì ta cho nhảy lên tổ tiên thứ của nó.
int par[N], up[N][17];
void preprocess() {
for (int u = 1; u <= n; ++u) up[u][0] = par[u];
for (int j = 1; j < 17; ++j)
for (int u = 1; u <= n; ++u)
up[u][j] = up[up[u][j - 1]][j - 1];
}
int ancestor_k(int u, int k) {
for (int j = 0; (1 << j) <= k; ++j)
if (k >> j & 1) u = up[u][j];
return u;
}
Qua đó, ta có thể thấy rằng Binary Lifting chỉ đơn giản là một cách tiền xử lý dữ liệu nhằm giúp cho thời gian truy vấn tối ưu hơn. Về tính chất, Binary Lifting khá giống với chặt nhị phân, khác ở chỗ mỗi lần, Binary Lifting thì ta thử nhảy đơn vị, còn chặt nhị phân thì ta thử nhảy đơn vị.
¶ Bài toán 2
Cho một cây có trọng số gồm đỉnh có gốc tại đỉnh . Có truy vấn, mỗi truy vấn gồm cặp số , ta cần in ra là tổ tiên xa nhất của thỏa tổng trọng số trên đường đi từ đến . Giới hạn:
¶ Thuật toán 1
Ta xây dựng mảng là khoảng cách từ đến tổ tiên thứ của .
Cách làm dễ nhận ra là chặt nhị phân giá trị của , sau đó so sánh với khoảng cách từ đến tổ tiên thứ của .
int dist[N][17];
int calc_dist(int u, int k) {
int sum = 0;
for (int j = 0; (1 << j) <= k; ++j)
if (k >> j & 1) {
sum += dist[u][j];
u = up[u][j];
}
return sum;
}
int solve(int u, int x) {
int lo = 0, hi = h[u], mid, ans = 0;
while (lo <= hi) {
mid = (lo + hi) / 2;
if (calc_dist(u, mid) <= x) {
ans = mid;
lo = mid + 1;
}
else hi = mid - 1;
}
return ancestor_k(u, ans);
}
¶ Phân tích
- Độ phức tạp tiền xử lý: (tạo mảng và )
- Độ phức tạp truy vấn: (chặt nhị phân) (tính khoảng cách) =
- Có truy vấn, vì thế tổng độ phức tạp là
¶ Thuật toán 2
Ta có nhận xét:
- Ta đã tính trước các khoảng cách có độ lớn (mảng )
- Từ đó, ta có thể nhảy theo từng bước để tính khoảng cách trong
int dist[N][17];
int solve(int u, int x) {
int now_dist = 0, k = 0;
for (int j = __lg(h[u]); j >= 0; --j) {
// nếu khoảng cách từ u ban đầu đến tổ tiên thứ (k + 2^j) <= x
if (h[u] >= (1 << j) && now_dist + dist[u][j] <= x) {
now_dist += dist[u][j];
k |= 1 << j;
u = up[u][j];
}
}
return u;
}
¶ Phân tích
- Độ phức tạp tiền xử lý: (tạo mảng và )
- Độ phức tạp truy vấn: (chặt nhị phân) (tính khoảng cách) =
- Có truy vấn, vì thế tổng độ phức tạp là
¶ Ứng dụng Binary Lifting vào bài toán LCA
Dễ thấy: nếu là tổ tiên chung của và ( gốc) thì cũng là tổ tiên chung của và . Do đó, ta có thể tìm tổ tiên chung gần nhất của và bằng Binary Lifting.
Bằng cách sử dụng mảng , ta có thể nhảy từ đến bất kì tổ tiên nào chỉ trong (bài toán tìm tổ tiên thứ ). Ta có thể tính mảng này bằng hàm như sau:
void dfs(int u) {
for (int v : g[u]) {
if (v == up[u][0]) continue;
h[v] = h[u] + 1;
up[v][0] = u;
for (int j = 1; j < 20; ++j)
up[v][j] = up[up[v][j - 1]][j - 1];
dfs(v);
}
}
Bước khởi tạo này chi phí bộ nhớ lẫn thời gian.
Cách tìm LCA giống hệt thuật toán ngây thơ 1, nhưng để tăng tốc, thay vì nhảy lên cha ở mỗi bước, ta dùng mảng để nhảy, từ đó thu được độ phức tạp cho mỗi truy vấn. Cụ thể:
-
Gọi là độ cao của đỉnh . Để tính , giả sử , đầu tiên ta tìm là tổ tiên của và có :
- Rõ ràng, ta cần nhảy từ lên cha thứ .
-
Sau khi và đã ở cùng độ cao, ta sẽ tính :
- Nếu thì chính là và .
- Nếu thì ta dùng Binary Lifting để tìm lớn nhất sao cho tổ tiên thứ của và khác nhau (không phải tổ tiên chung). Lúc này, tổ tiên thứ chính là tổ tiên chung của và .
- Ta duyệt từ về
- Nếu tổ tiên thứ của và khác nhau thì ta cho cả và nhảy lên tổ tiên thứ của chúng. Cuối cùng thì và sẽ có cùng cha (tổ tiên thứ là cha của tổ tiên thứ ), vậy nên khi đó .
int h[N], up[N][20];
int lca(int u, int v) {
if (h[u] != h[v]) {
if (h[u] < h[v]) swap(u, v);
// Tìm tổ tiên u' của u sao cho h(u') = h(v)
int k = h[u] - h[v];
for (int j = 0; (1 << j) <= k; ++j)
if (k >> j & 1) // Nếu bit thứ j của k là 1
u = up[u][j];
}
if (u == v) return u;
// Tìm lca(u, v)
int k = __lg(h[u]);
for (int j = k; j >= 0; --j)
if (up[u][j] != up[v][j]) // Nếu tổ tiên thứ 2^j của u và v khác nhau
u = up[u][j], v = up[v][j];
return up[u][0];
}
¶ Phân tích:
- Độ phức tạp tiền xử lý:
- Độ phức tạp khi truy vấn:
- Có truy vấn, vì thế tổng độ phức tạp là
¶ Bài toán 1
¶ Tóm tắt
Cho cây đỉnh có trọng số . Cần trả lời truy vấn, mỗi truy vấn yêu cầu tìm khoảng cách giữa 2 đỉnh và trong cây.
¶ Ý tưởng
Chọn đỉnh làm gốc của cây.
Với mỗi đỉnh của cây, ta tính là khoảng cách của mỗi đỉnh đến đỉnh bằng cách duyệt qua tất cả các đỉnh trong cây.
Với hai đỉnh và bất kì, xét đường đi từ gốc của cây đến hai đỉnh này. Ta nhận thấy:
- Phần giao của hai đường đi chính là đường đi từ gốc của cây đến tổ tiên chung gần nhất của và - gọi đỉnh này là .
- Hiệu giữa phần giao và mỗi đường đi ban đầu là đường đi từ đến và đường đi từ đến .
Từ hai quan sát trên, thấy được chỉ cần ba giá trị , và để tính . Khi cộng và , các đỉnh thuộc phần giao bị tính đến 2 lần, vì vậy ta tính .
¶ Cài đặt
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int N = 1000 + 3;
int n, q;
struct Edge {
int v, w;
Edge(int v = 0, int w = 0) : v(v), w(w) {}
};
vector<Edge> g[N];
int h[N], f[N], up[N][10];
void dfs(int u) {
for (Edge &e : g[u]) {
int v = e.v, w = e.w;
if (v == up[u][0]) continue;
h[v] = h[u] + 1;
f[v] = f[u] + w;
up[v][0] = u;
for (int j = 1; j < 10; ++j)
up[v][j] = up[up[v][j - 1]][j - 1];
dfs(v);
}
}
int lca(int u, int v) {
if (h[u] != h[v]) {
if (h[u] < h[v]) swap(u, v);
int k = h[u] - h[v];
for (int j = 0; (1 << j) <= k; ++j)
if (k >> j & 1)
u = up[u][j];
}
if (u == v) return u;
int k = __lg(h[u]);
for (int j = k; j >= 0; --j)
if (up[u][j] != up[v][j])
u = up[u][j], v = up[v][j];
return up[u][0];
}
int dist(int u, int v) {
int p = lca(u, v);
return f[u] + f[v] - 2 * f[p];
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> q;
for (int i = 1, u, v, c; i < n; ++i) {
cin >> u >> v >> c;
g[u].emplace_back(v, c);
g[v].emplace_back(u, c);
}
dfs(1);
int u, v; while (q--) {
cin >> u >> v;
cout << dist(u, v) << '\n';
}
}
¶ Bài toán 2
¶ Tóm tắt
Cho cây đỉnh và một số nguyên dương là số nhóm . Đỉnh thứ thuộc nhóm .
Output gồm dòng, dòng thứ chứa số nguyên dương là khoảng cách xa nhất giữa đỉnh bất kì thuộc nhóm thứ .
¶ Ý tưởng
- Với bài toán tìm khoảng cách xa nhất giữa 2 đỉnh trên cây, ta có thể làm như sau
- Bước 1: Chọn 1 đỉnh bất kì, đặt là đỉnh .
- Bước 2: Tìm đỉnh bất kì xa đỉnh nhất, đặt là .
- Bước 3: Tìm đỉnh bất kì xa đỉnh nhất, đặt là .
- Lúc này, khoảng cách giữa đỉnh và chính là khoảng cách xa nhất giữa đỉnh trên cây và được định nghĩa là đường kính của cây.
- Chứng minh thuật toán: here (Exercise 9-1).
¶ Thuật toán
Từ bài toán trên, ta có thể tìm khoảng cách lớn nhất giữa 2 đỉnh thuộc mỗi nhóm như sau:
- Bước 1: Chọn 1 đỉnh bất kì thuộc nhóm, đặt là .
- Bước 2: Tìm đỉnh bất kì thuộc nhóm xa đỉnh nhất, đặt là .
- Bước 3: Tìm khoảng cách lớn nhất từ đỉnh đến các đỉnh thuộc nhóm còn lại.
¶ Cài đặt
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int N = 2e5 + 8;
int n, k, root;
vector<int> g[N], group[N >> 1];
int h[N], up[N][18];
void dfs(int u) {
for (int v : g[u]) {
h[v] = h[u] + 1;
for (int j = 1; j < 18; ++j)
up[v][j] = up[up[v][j - 1]][j - 1];
dfs(v);
}
}
int lca(int u, int v) {
if (h[u] != h[v]) {
if (h[u] < h[v]) swap(u, v);
int k = h[u] - h[v];
for (int j = 0; (1 << j) <= k; ++j)
if (k >> j & 1)
u = up[u][j];
}
if (u == v) return u;
int k = __lg(h[u]);
for (int j = k; j >= 0; --j)
if (up[u][j] != up[v][j])
u = up[u][j], v = up[v][j];
return up[u][0];
}
int dist(int u, int v) {
int p = lca(u, v);
return h[u] + h[v] - 2 * h[p];
}
int diameter(vector<int> &meeting) {
int A = meeting[0], max_dist = 0, B = A, d;
for (int x : meeting) {
d = dist(A, x);
if (max_dist < d) {
max_dist = d;
B = x;
}
}
max_dist = 0;
for (int x : meeting) {
d = dist(B, x);
max_dist = max(max_dist, d);
}
return max_dist;
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> k;
for (int i = 1, x; i <= n; ++i) {
cin >> x >> up[i][0];
group[x].push_back(i);
g[up[i][0]].push_back(i);
if (up[i][0] == 0) root = i;
}
dfs(root);
for (int i = 1; i <= k; ++i)
cout << diameter(group[i]) << '\n';
}
¶ Bài toán 3
¶ Tóm tắt
Cho cây đỉnh có gốc là đỉnh và truy vấn thuộc trong loại:
- : Chọn làm gốc của cây.
- : Tìm tổ tiên chung gần nhất của đỉnh và .
Giới hạn:
¶ Thuật toán
- Xét cây có gốc là đỉnh bất kì (giả sử là đỉnh ), trong đỉnh , , sẽ luôn tồn tại ít nhất đỉnh trùng nhau, đỉnh còn lại chính là trong cây có gốc là .
- Phần chứng minh khá dễ, xin phép nhường lại cho bạn đọc như một bài tập.
¶ Cài đặt
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1e5 + 9;
int n;
vector<int> g[N];
int h[N], up[N][17];
void dfs(int u) {
for (int v : g[u]) {
if (v == up[u][0]) continue;
h[v] = h[u] + 1;
up[v][0] = u;
for (int j = 1; j < 17; ++j)
up[v][j] = up[up[v][j - 1]][j - 1];
dfs(v);
}
}
int lca(int u, int v) {
if (h[u] != h[v]) {
if (h[u] < h[v]) swap(u, v);
int k = h[u] - h[v];
for (int j = 0; (1 << j) <= k; ++j)
if (k >> j & 1)
u = up[u][j];
}
if (u == v) return u;
int k = __lg(h[u]);
for (int j = k; j >= 0; --j)
if (up[u][j] != up[v][j])
u = up[u][j], v = up[v][j];
return up[u][0];
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
while (cin >> n, n) {
for (int i = 1; i <= n; ++i) g[i].clear();
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
char c;
int m, root(1), u, v; cin >> m; while (m--) {
cin >> c;
if (c == '!') cin >> root;
else {
cin >> u >> v;
int uv = lca(u, v);
int ur = lca(u, root);
int vr = lca(v, root);
cout << (uv ^ ur ^ vr) << '\n';
}
}
}
}