Tác giả:
Reviewer:
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:
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 $\log_2$ 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;
}
Cho một cây gồm $N$ đỉnh có gốc tại đỉnh $1$. Có $Q$ truy vấn, mỗi truy vấn gồm $1$ cặp số $(u, v)$ và ta cần tìm LCA của $u$ và $v$, tức là tìm một đỉnh $w$ xa gốc nhất nằm trên đường đi từ $u$ và $v$ đến gốc. Đặc biệt, nếu $u$ là tổ tiên của $v$, thì $u$ là LCA của $u$ và $v$.
Giới hạn: $N, Q \leq 2 \cdot 10^5$
Ví dụ:
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;
}
Đố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.
Đầu tiên, ta sẽ tìm hiểu về ý tưởng của Binary Lifting qua bài toán con của $LCA$.
Cho một cây gồm $N$ đỉnh có gốc tại đỉnh $1$. Có $Q$ truy vấn, mỗi truy vấn gồm $1$ cặp số $(u, k)$, ta cần in ra tổ tiên thứ $k$ của $u$ (tổ tiên thứ $k$ của $u$ là $par[par[\ldots[u \underset{\color{blue}{k \text{ lần}}}{\color{blue}{\underbrace{\color{blue}{]\ldots]]}}}}$ ).
Giới hạn: $N, Q \leq 10^5$
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;
}
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?
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;
}
Ta còn có thể tối ưu thời gian truy vấn được hay không?
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;
}
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 $8$).
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;
}
Nếu ta làm tiếp như thuật toán tối ưu $1.3$ (tiếp tục tạo các mảng $up16, up32, \dots, up65536$) ta sẽ có $\log_2(N)$ mảng up, độ phức tạp bài toán lúc này như sau:
Nhưng nếu dùng $\log_2$ mảng $up$ sẽ mang đến cho ta nhiều bất tiện (code dài, dễ sai,…). Do đó, ta có thể đặt:
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;
}
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ụ: $25 = 2^4 + 2^3 + 2^0 = 11001_2$.
Từ nhận xét trên, ta có một cách khác để nhảy lên tổ tiên thứ $k$ của $u$ là duyệt $j$ từ $0$ đến $\log_2(k)$, nếu bit thứ $j$ của $k$ là $1$ thì ta cho $u$ nhảy lên tổ tiên thứ $2^j$ 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 $2^k$ đơn vị, còn chặt nhị phân thì ta thử nhảy $\frac{hi - lo + 1}{2}$ đơn vị.
Cho một cây có trọng số gồm $N$ đỉnh có gốc tại đỉnh $1$. Có $Q$ truy vấn, mỗi truy vấn gồm $1$ cặp số $(u, x)$, ta cần in ra $v$ là tổ tiên xa nhất của $u$ thỏa tổng trọng số trên đường đi từ $u$ đến $v$ $\leq x$. Giới hạn: $N, Q \leq 10^5$
Ta xây dựng mảng $dist[u][j]$ là khoảng cách từ $u$ đến tổ tiên thứ $2^j$ của $u$.
Cách làm dễ nhận ra là chặt nhị phân giá trị của $k$, sau đó so sánh $x$ với khoảng cách từ $u$ đến tổ tiên thứ $k$ của $u$.
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);
}
Ta có nhận xét:
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;
}
Dễ thấy: nếu $x$ là tổ tiên chung của $u$ và $v$ ($x \neq$ gốc) thì $par[x]$ cũng là tổ tiên chung của $u$ và $v$. Do đó, ta có thể tìm tổ tiên chung gần nhất của $u$ và $v$ bằng Binary Lifting.
Bằng cách sử dụng mảng $up$, ta có thể nhảy từ $u$ đến bất kì tổ tiên nào chỉ trong $\mathcal{O}(\log N)$ (bài toán tìm tổ tiên thứ $k$). Ta có thể tính mảng này bằng hàm $DFS$ 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í $\mathcal{O}(N\log N)$ 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 $up$ để nhảy, từ đó thu được độ phức tạp $\mathcal{O}(\log N)$ cho mỗi truy vấn. Cụ thể:
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];
}
Cho $1$ cây $N$ đỉnh có trọng số $(N \le 1000)$. Cần trả lời $Q$ truy vấn, mỗi truy vấn yêu cầu tìm khoảng cách giữa 2 đỉnh $u$ và $v$ trong cây.
Chọn đỉnh $1$ làm gốc của cây. Với mỗi đỉnh của cây, ta tính $f(u)$ là khoảng cách của mỗi đỉnh đến đỉnh $1$ bằng cách duyệt qua tất cả các đỉnh trong cây.
Với hai đỉnh $u$ và $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:
Từ hai quan sát trên, thấy được chỉ cần ba giá trị $f(u)$, $f(v)$ và $f(p)$ để tính $dist(u, v)$. Khi cộng $f(u)$ và $f(v)$, các đỉnh thuộc phần giao bị tính đến 2 lần, vì vậy ta tính $dist(u, v) = f(u) + f(v) - 2 * f(p)$.
#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';
}
}
Cho $1$ cây $N$ đỉnh và một số nguyên dương $K$ là số nhóm $(N \le 2\cdot 10^5, K \le \frac{N}{2})$. Đỉnh thứ $i$ thuộc nhóm $x_i$.
Output gồm $K$ dòng, dòng thứ $i$ chứa $1$ số nguyên dương là khoảng cách xa nhất giữa $2$ đỉnh bất kì thuộc nhóm thứ $i$.
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:
#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';
}
Cho $1$ cây $N$ đỉnh có gốc là đỉnh $1$ và $M$ truy vấn thuộc $1$ trong $2$ loại:
Giới hạn: $N, M \le 10^5$
#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';
}
}
}
}