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 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 đỉ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:
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 .
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:
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
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
Nhưng nếu dùng
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ụ:
Từ nhận xét trên, ta có một cách khác để nhảy lên tổ tiên thứ
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
Cho một cây có trọng số gồm
Ta xây dựng mảng
Cách làm dễ nhận ra là chặt nhị phân giá trị 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);
}
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
Bằng cách sử dụng mảng
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í
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
Gọi
Sau 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];
}
Cho
Chọn đỉnh
Với mỗi đỉnh của cây, ta tính
Với hai đỉnh
Từ hai quan sát trên, thấy được chỉ cần ba giá trị
#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
Output gồm
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
Giới hạn:
#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';
}
}
}
}