uniolympiads Ελληνικά

Lowest common ancestor (binary lifting)

The 2k2^k-th ancestor of every vertex in a table. With it, kk-th ancestor, LCA and tree distance, each in O(log⁡n)O(\log n).

When

Queries on a tree: "who is the kk-th boss of vv?", "who is the common boss of aa and bb?", "how many edges apart are aa and bb?".

The idea

up0[v]\mathrm{up}_0[v] is the parent of vv, and upk[v]=upk−1[upk−1[v]]\mathrm{up}_k[v] = \mathrm{up}_{k-1}[\mathrm{up}_{k-1}[v]]: two jumps of 2k−12^{k-1} make one of 2k2^k. The root is its own ancestor, so jumps that would leave the tree stop there.

  • kk-th ancestor: write kk in binary and make one jump for each set bit.
  • LCA: first bring aa and bb to the same depth. If they coincide, you are done. Otherwise, from the largest kk down, jump with both together while their ancestors differ. At the end they are children of the LCA.
  • Distance: depth(a)+depth(b)−2 depth(lca(a,b))\mathrm{depth}(a) + \mathrm{depth}(b) - 2\,\mathrm{depth}(\mathrm{lca}(a, b)).

Depths and parents come from a BFS, not a recursive DFS. In Company Queries the tree can be a chain of length 2⋅1052 \cdot 10^5.

Pitfalls

  • The "while they differ" move is the whole point. If you jump while they are equal, you overshoot the LCA and end at the root.
  • In Company Queries I the kk-th boss may not exist (answer −1-1). Check k>depth(v)k > \mathrm{depth}(v) before jumping, because the code here silently stops at the root.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/lca.cpp
// Lowest common ancestor with binary lifting. Build O(n log n), query O(log n).
// up[k][v] = the 2^k-th ancestor of v (the root is its own ancestor).
// The tree is given as an adjacency list; depths come from an iterative BFS.

struct LCA {
    int n;
    int LOG;
    vector<vector<int>> up;
    vector<int> depth;

    LCA(const vector<vector<int>>& adj, int root) : n(adj.size()), depth(adj.size(), -1) {
        LOG = 1;
        while ((1 << LOG) < n) {
            LOG++;
        }
        up.assign(LOG + 1, vector<int>(n, root));
        queue<int> q;
        depth[root] = 0;
        q.push(root);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (depth[v] == -1) {
                    depth[v] = depth[u] + 1;
                    up[0][v] = u;
                    q.push(v);
                }
            }
        }
        for (int k = 1; k <= LOG; k++) {
            for (int v = 0; v < n; v++) {
                up[k][v] = up[k - 1][up[k - 1][v]];
            }
        }
    }

    int kthAncestor(int v, int k) {
        for (int j = 0; j <= LOG; j++) {
            if ((k >> j) & 1) {
                v = up[j][v];
            }
        }
        return v;
    }

    int lca(int a, int b) {
        if (depth[a] < depth[b]) {
            swap(a, b);
        }
        a = kthAncestor(a, depth[a] - depth[b]);
        if (a == b) {
            return a;
        }
        for (int k = LOG; k >= 0; k--) {
            if (up[k][a] != up[k][b]) {
                a = up[k][a];
                b = up[k][b];
            }
        }
        return up[0][a];
    }

    int distance(int a, int b) {
        return depth[a] + depth[b] - 2 * depth[lca(a, b)];
    }
};

Tested on 500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.