Lowest Common Ancestor (LCA)

The Lowest Common Ancestor (LCA) of two nodes $u$ and $v$ in a tree is the deepest node that is an ancestor of both $u$ and $v$.

Method 1: Binary Lifting

• Preprocessing: $O(n \log n)$
• Query: $O(\log n)$

Implementation

const int LOG = 20;
class LCA {
    int n;
    vector<vector<int>> adj;
    vector<vector<int>> up;
    vector<int> depth;
public:
    LCA(int n) : n(n), adj(n), up(n, vector<int>(LOG, -1)), depth(n) {}
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void build(int root = 0) {
        function<void(int, int, int)> dfs = [&](int u, int p, int d) {
            up[u][0] = p;
            depth[u] = d;
            for (int j = 1; j < LOG; j++) {
                if (up[u][j-1] != -1) {
                    up[u][j] = up[up[u][j-1]][j-1];
                }
            }
            for (int v : adj[u]) {
                if (v != p) {
                    dfs(v, u, d + 1);
                }
            }
        };
        dfs(root, -1, 0);
    }
    int getAncestor(int v, int k) {
        for (int j = 0; j < LOG && v != -1; j++) {
            if (k & (1 << j)) {
                v = up[v][j];
            }
        }
        return v;
    }
    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        u = getAncestor(u, depth[u] - depth[v]);
        if (u == v) return u;
        for (int j = LOG - 1; j >= 0; j--) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
        return up[u][0];
    }
    int distance(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
    }
};

Method 2: Euler Tour + RMQ (Sparse Table)

• Preprocessing: $O(n \log n)$
• Query: $O(1)$

Idea

1. Perform an Euler tour of the tree.
2. The LCA of $u$ and $v$ is the node with the minimum depth between their first occurrences in the tour.

Implementation

class LCA_RMQ {
    int n, LOG;
    vector<vector<int>> adj;
    vector<int> euler, first, depth;
    vector<vector<int>> sparse;
    void dfs(int u, int p, int d) {
        first[u] = euler.size();
        euler.push_back(u);
        depth[u] = d;
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1);
                euler.push_back(u);
            }
        }
    }
    void buildSparse() {
        int m = euler.size();
        LOG = 32 - __builtin_clz(m);
        sparse.assign(m, vector<int>(LOG));
        for (int i = 0; i < m; i++) {
            sparse[i][0] = i;
        }
        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i + (1 << j) <= m; i++) {
                int left = sparse[i][j-1];
                int right = sparse[i + (1 << (j-1))][j-1];
                sparse[i][j] = (depth[euler[left]] < depth[euler[right]]) ? left : right;
            }
        }
    }
public:
    LCA_RMQ(int n) : n(n), adj(n), first(n), depth(n) {}
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void build(int root = 0) {
        euler.clear();
        dfs(root, -1, 0);
        buildSparse();
    }
    int query(int u, int v) {
        int l = first[u], r = first[v];
        if (l > r) swap(l, r);
        int len = r - l + 1;
        int k = 31 - __builtin_clz(len);
        int left = sparse[l][k];
        int right = sparse[r - (1 << k) + 1][k];
        return (depth[euler[left]] < depth[euler[right]]) ? euler[left] : euler[right];
    }
    int distance(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
    }
};

Method 3: Tarjan’s Offline LCA

• Suitable for answering multiple queries offline.
• Time: $O((n + q) \cdot \alpha(n))$, where $\alpha$ is the inverse Ackermann function.

Implementation

class TarjanLCA {
    int n;
    vector<vector<int>> adj;
    vector<vector<pair<int, int>>> queries;
    vector<int> parent, rank_, ancestor;
    vector<bool> visited;
    vector<int> answer;
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
    }
    void dfs(int u, int p) {
        ancestor[find(u)] = u;
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u);
                unite(u, v);
                ancestor[find(u)] = u;
            }
        }
        visited[u] = true;
        for (auto& [v, idx] : queries[u]) {
            if (visited[v]) {
                answer[idx] = ancestor[find(v)];
            }
        }
    }
public:
    TarjanLCA(int n, int q) : n(n), adj(n), queries(n), parent(n), rank_(n, 0), ancestor(n), visited(n, false), answer(q) {
        iota(parent.begin(), parent.end(), 0);
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void addQuery(int u, int v, int idx) {
        queries[u].push_back({v, idx});
        queries[v].push_back({u, idx});
    }
    vector<int> solve(int root = 0) {
        dfs(root, -1);
        return answer;
    }
};

Applications

• Finding distances between nodes
• Path queries
• Many tree algorithms rely on efficient LCA computation.