Hướng giải của Tổ tiên chung

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Bài toán tìm tổ tiên chung gần nhất (LCA) cơ bản trên cây. Chúng ta sử dụng thuật toán Binary Lifting. DFS để tính toán chiều sâu depth[u] và bảng cha nhị phân up[u][k]. Để tìm LCA của u và v:

  1. Đưa hai đỉnh lên cùng chiều sâu bằng các bước nhảy nhị phân.
  2. Nếu hai đỉnh đã gặp nhau, trả về đỉnh đó.
  3. Đồng loạt nhảy hai đỉnh lên trên cao nhất có thể sao cho up[u][k] != up[v][k]. Sau vòng lặp, LCA sẽ là cha trực tiếp của u.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        if (cin >> u >> v) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }
    vector<int> depth(n + 1, 0);
    vector<vector<int>> up(n + 1, vector<int>(LOG, 0));

    auto dfs = [&](auto self, int u, int p) -> void {
        depth[u] = depth[p] + 1;
        up[u][0] = p;
        for (int k = 1; k < LOG; k++) {
            up[u][k] = up[up[u][k-1]][k-1];
        }
        for (int v : adj[u]) {
            if (v != p) {
                self(self, v, u);
            }
        }
    };

    depth[0] = -1;
    dfs(dfs, 1, 0);

    auto lca = [&](int u, int v) -> int {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOG; k++) {
            if (diff & (1 << k)) {
                u = up[u][k];
            }
        }
        if (u == v) return u;
        for (int k = LOG - 1; k >= 0; k--) {
            if (up[u][k] != up[v][k]) {
                u = up[u][k];
                v = up[v][k];
            }
        }
        return up[u][0];
    };

    for (int i = 0; i < q; i++) {
        int u, v;
        if (cin >> u >> v) {
            cout << lca(u, v) << "\n";
        }
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.