BOJ. LCA (11437)

Problem: BOJ 11437 — Lowest Common Ancestor · 한국어 · 日本語

Root the tree at node 1. An iterative breadth-first traversal records each node’s depth and its immediate parent; the root’s parent is 0, a sentinel whose ancestors are also 0. Because the input is a tree, each non-root node is reached from exactly one parent. Using a queue instead of recursive DFS keeps traversal safe even when the tree is a chain of 50,000 nodes.

Let ancestor[v][j] be the node reached by moving 2^j edges upward from v. The immediate-parent traversal fills level 0; then ancestor[v][j] = ancestor[ancestor[v][j - 1]][j - 1] builds each higher level. The sentinel makes this recurrence valid at the root as well.

For a query, first lift the deeper node by the depth difference so both nodes are at the same level. If they are now equal, that node is the LCA. Otherwise, inspect jump levels from largest to smallest, moving both nodes upward whenever their ancestors at that level differ. They then sit immediately below their lowest common ancestor, so their immediate parent is the answer.

Preprocessing takes O(N log N) time and memory; each query takes O(log N) time.

C++17

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    constexpr int LOG = 17;  // 2^16 >= 50,000
    vector<int> depth(n + 1, -1);
    vector<vector<int>> ancestor(LOG, vector<int>(n + 1, 0));

    queue<int> pending;
    depth[1] = 0;
    pending.push(1);

    while (!pending.empty()) {
        int node = pending.front();
        pending.pop();

        for (int next : graph[node]) {
            if (next == ancestor[0][node]) {
                continue;
            }
            ancestor[0][next] = node;
            depth[next] = depth[node] + 1;
            pending.push(next);
        }
    }

    for (int level = 1; level < LOG; ++level) {
        for (int node = 1; node <= n; ++node) {
            ancestor[level][node] =
                ancestor[level - 1][ancestor[level - 1][node]];
        }
    }

    auto lca = [&](int a, int b) {
        if (depth[a] < depth[b]) {
            swap(a, b);
        }

        int difference = depth[a] - depth[b];
        for (int level = 0; level < LOG; ++level) {
            if (difference & (1 << level)) {
                a = ancestor[level][a];
            }
        }

        if (a == b) {
            return a;
        }

        for (int level = LOG - 1; level >= 0; --level) {
            if (ancestor[level][a] != ancestor[level][b]) {
                a = ancestor[level][a];
                b = ancestor[level][b];
            }
        }
        return ancestor[0][a];
    };

    int queries;
    cin >> queries;
    while (queries--) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
}