Hướng dẫn giải của Nút cha chung gần nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm nút cha chung gần nhất (Lowest Common Ancestor - LCA) của hai nút cho trước trong một cây có nút gốc là K. Cây được biểu diễn bằng danh sách kề N-1 cạnh. Nút cha chung gần nhất là nút nằm sâu nhất (gần hai nút nhất) trên đường đi từ gốc đến cả hai nút đó.
Các cách tiếp cận
Cách Nâng cao và hạ thấp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
vector<int> adj[MAXN];
int parent[MAXN];
int depth[MAXN];
void dfs(int u, int p) {
parent[u] = p;
for (int v : adj[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
int lca(int u, int v) {
// Đưa u, v về cùng độ sâu
while (depth[u] > depth[v]) u = parent[u];
while (depth[v] > depth[u]) v = parent[v];
// Nâng cả hai cho tới khi trùng
while (u != v) {
u = parent[u];
v = parent[v];
}
return u;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
for (int i = 0; i < N - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
// Tìm cha và độ sâu
depth[K] = 0;
dfs(K, 0);
int u, v;
cin >> u >> v;
cout << lca(u, v);
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Cách tiếp cận này sử dụng DFS để tiền xử lý cây, lưu lại cha và độ sâu của mỗi nút. Để tìm LCA của u và v, ta thực hiện hai bước:
- Nâng nút có độ sâu lớn hơn (u hoặc v) lên cho đến khi cả hai có cùng độ sâu.
- Nâng cả hai nút cùng lúc cho đến khi chúng gặp nhau. Nút đầu tiên chúng gặp nhau chính là LCA. Do cây có thể bị xiên (lệch độ sâu), độ phức tạp của truy vấn trong trường hợp xấu nhất là O(N).
Cách Binary Lifting (Nâng cao theo lũy thừa)
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 10005;
const int LOGN = 15; // 2^14 > 10000
vector<int> adj[MAXN];
int up[MAXN][LOGN]; // up[u][i] là cha 2^i bậc của u
int depth[MAXN];
int N, K;
void dfs(int u, int p) {
up[u][0] = p;
for (int i = 1; i < LOGN; i++) {
up[u][i] = up[up[u][i-1]][i-1];
}
for (int v : adj[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
int get_lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
// Nâng u lên để bằng độ sâu của v
for (int i = LOGN - 1; i >= 0; i--) {
if (depth[u] - (1 << i) >= depth[v]) {
u = up[u][i];
}
}
if (u == v) return u;
// Nâng cả hai lên cho đến khi cha của chúng là LCA
for (int i = LOGN - 1; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
depth[K] = 0;
dfs(K, 0);
int u, v;
cin >> u >> v;
cout << get_lca(u, v);
return 0;
}
- Time Complexity: O(N log N) tiền xử lý, O(log N) truy vấn
- Space Complexity: O(N log N)
Phương pháp này tối ưu hóa việc di chuyển trên cây bằng cách sử dụng các bước nhảy lũy thừa 2^i. Mảng up[u][i] lưu cha của nút u ở khoảng cách 2^i.
Quá trình tìm LCA:
- Chuẩn hóa độ sâu: Dùng mảng lũy thừa để nhảy lên nhanh chóng sao cho u và v có độ sâu bằng nhau. Ví dụ, nếu cần nâng u lên 13 bậc, ta nhảy 8 (2^3) bậc, sau đó 4 (2^2) bậc, rồi 1 (2^0) bậc.
- Tìm LCA: Tương tự, dùng lũy thừa để nhảy lên cùng lúc cho đến khi cha của u và v trùng nhau. Nút đó chính là LCA.
Phương pháp này cực kỳ hiệu quả cho các bài toán có nhiều truy vấn LCA hoặc cây lớn.
Cách Tối ưu O(1) với Euler Tour và Sparse Table
// Hàm tìm vị trí của giá trị nhỏ nhất trong mảng RMQ
pair<int, int> getMinPos(const vector<pair<int, int>>& arr, int L, int R) {
pair<int, int> minVal = {1e9, -1};
for (int i = L; i <= R; i++) {
if (arr[i].first < minVal.first) {
minVal = arr[i];
}
}
return minVal;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<vector<int>> adj(N + 1);
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Euler Tour: ghi lại thứ tự duyệt và độ sâu
vector<int> euler; // Danh sách các nút theo thứ tự Euler Tour
vector<int> first(N + 1); // Vị trí xuất hiện đầu tiên của mỗi nút
vector<int> depth(N + 1); // Độ sâu của mỗi nút
// DFS để tạo Euler Tour và RMQ
function<void(int, int, int)> dfs = [&](int u, int p, int d) {
depth[u] = d;
first[u] = euler.size();
euler.push_back(u);
for (int v : adj[u]) {
if (v != p) {
dfs(v, u, d + 1);
euler.push_back(u); // Quay lại cha sau khi duyệt xong con
}
}
};
dfs(K, 0, 0);
// Xây dựng Sparse Table cho RMQ
int m = euler.size();
int logm = log2(m) + 1;
vector<vector<int>> st(m, vector<int>(logm));
for (int i = 0; i < m; i++) st[i][0] = euler[i];
for (int j = 1; j < logm; j++) {
for (int i = 0; i + (1 << j) <= m; i++) {
int u = st[i][j-1];
int v = st[i + (1 << (j-1))][j-1];
// Chọn nút có độ sâu nhỏ hơn (gần gốc hơn)
if (depth[u] < depth[v]) st[i][j] = u;
else st[i][j] = v;
}
}
int u, v;
cin >> u >> v;
int l = first[u];
int r = first[v];
if (l > r) swap(l, r);
// Tìm độ sâu tối thiểu trong khoảng [l, r]
int len = r - l + 1;
int k = log2(len);
int node1 = st[k][l];
int node2 = st[k][r - (1 << k) + 1];
int lca = (depth[node1] < depth[node2]) ? node1 : node2;
cout << lca;
return 0;
}
- Time Complexity: O(N log N) tiền xử lý, O(1) truy vấn
- Space Complexity: O(N log N)
Phương pháp này sử dụng Euler Tour để chuyển bài toán LCA thành bài toán Range Minimum Query (RMQ).
- Euler Tour: Thực hiện DFS và ghi lại thứ tự các nút khi đi qua. Khi đi từ cha xuống con, ghi nút con. Khi quay lại từ con lên cha, ghi nút cha. Tạo ra một mảng các nút.
- First Array: Lưu vị trí đầu tiên mỗi nút xuất hiện trong mảng Euler Tour.
- RMQ: Xây dựng Sparse Table cho mảng Euler Tour, nhưng giá trị lưu không phải là chỉ số mà là nút có độ sâu nhỏ nhất trong đoạn.
Để tìm LCA của u và v, ta chỉ cần tìm đoạn [First[u], First[v]] (hoặc ngược lại) trong mảng Euler Tour, và tìm nút có độ sâu nhỏ nhất trong đoạn đó. Nhờ Sparse Table, ta có thể làm việc này trong thời gian O(1).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N) | O(N) | Nâng cao và hạ thấp |
| 2 | O(N log N) tiền xử lý, O(log N) truy vấn | O(N log N) | Binary Lifting (Nâng cao theo lũy thừa) |
| 3 | O(N log N) tiền xử lý, O(1) truy vấn | O(N log N) | Tối ưu O(1) với Euler Tour và Sparse Table |
Bài học kinh nghiệm
- Vấn đề có thể được rút gọn thành tìm đường đi từ gốc đến các nút và so sánh.
- Phương pháp Binary Lifting là lựa chọn tối ưu cho bài toán này về độ cân bằng giữa độ phức tạp và khả năng cài đặt.
- Biến đổi bài toán thành Range Minimum Query (RMQ) cho phép truy vấn trong thời gian O(1) nhưng tốn nhiều thời gian tiền xử lý.
Lỗi thường gặp
- Quên khởi tạo độ sâu của nút gốc (K) bằng 0 hoặc 1 tùy mô hình.
- Lựa chọn sai độ lớn mảng (cần N <= 10000, nhưng trong code mẫu đôi khi dùng lớn hơn cho an toàn).
- Trong Binary Lifting, sai số tính toán chỉ số mảng (off-by-one error) hoặc lặp sai thứ tự (nên lặp từ log về 0).
- Nhập sai thứ tự cạnh (u, v) có thể gây tràn ngăn xếp (stack overflow) nếu dùng DFS đệ quy mà không kiểm tra cha.
Bình luận