Chapter 10 · Lowest Common Ancestor
LCA by Binary Lifting
The 12-line precomputation, the two-phase query, and the family of problems it solves beyond LCA.
up[v][j] = the 2j-th ancestor of v. Then up[v][j] = up[up[v][j-1]][j-1] — "halfway up, then halfway again", which is the whole idea.
const int LOG = 20; // 2^20 > 10^6 vertices
vector<array<int, LOG>> up(n);
vector<int> depth(n);
void dfs(int v, int p) {
up[v][0] = p == -1 ? v : p;
for (int j = 1; j < LOG; j++) up[v][j] = up[up[v][j-1]][j-1];
for (int to : g[v]) if (to != p) { depth[to] = depth[v] + 1; dfs(to, v); }
}
int lift(int v, int k) { // k-th ancestor of v (k <= depth[v])
for (int j = 0; j < LOG; j++) if (k >> j & 1) v = up[v][j];
return v;
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
a = lift(a, depth[a] - depth[b]); // phase 1: equalise depths
if (a == b) return a;
for (int j = LOG - 1; j >= 0; j--) // phase 2: descend together
if (up[a][j] != up[b][j]) { a = up[a][j]; b = up[b][j]; }
return up[a][0]; // one step above both
}After phase 1, depth(a) = depth(b), and lca(a,b) = lca(original a, original b) is unchanged (lifting an ancestor-side vertex to the other's depth cannot pass the LCA). In phase 2 the invariant is "a and b have equal depth and lca(a,b) is a proper ancestor of both"; each accepted jump preserves it, and after the loop a and b are the two children just below the LCA.
Phase 1: lifting a to depth depth(b) keeps the LCA because depth(lca) ≤ depth(b), so we stop at or below it. Phase 2: if up[a][j] ≠ up[b][j], both those ancestors are strictly below the LCA (otherwise, having equal depth and one common ancestor at that level, they would coincide) — so the jump cannot overshoot. Conversely, for every j with up[a][j] = up[b][j] the LCA is at or above that ancestor, so skipping those jumps loses nothing. Descending j from LOG-1 to 0 therefore accumulates exactly depth(a) - depth(lca) - 1 on each side. ∎
Largest-jump-first is a binary representation greedy: depth difference = ∑j bj 2j, so taking big jumps whenever they fit is exactly reading the bits. Low-to-high also works for lift (it is the same sum) but not for phase 2 — the invariant "still strictly below the LCA" is only maintained when you never overshoot, which requires descending powers. This asymmetry is the bug in most broken implementations.
#Distances and the k-th vertex on a path
int dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
// k-th vertex on the simple path a -> b (0 = a), k <= dist(a,b)
int kth_on_path(int a, int b, int k) {
int c = lca(a, b), up_len = depth[a] - depth[c];
return k <= up_len ? lift(a, k) : lift(b, dist(a, b) - k);
}
// vertex just below c on the path c -> x (needed for "which subtree contains x"):
int below(int c, int x) { return lift(x, depth[x] - depth[c] - 1); }The same table answers far more
- k-th ancestor / "who is d steps up from v" —
lift, O(log n), - diameter of a set of vertices: lift-based farthest-pair queries reduce to max over a set with LCA distances,
- jump through a functional graph with cycle handling (Functional and Permutation Graphs) — identical code,
up[v][0] = f[v], - binary lifting on a dynamic DSU ("successor after deletions", "the day two nodes became connected" — offline parallel binary search),
- max edge on a path: add a
mx[v][j]array alongsideup, combining with max — this is the same table, one more dimension, and it is the reason Heavy-Light Decomposition is only needed when updates are involved, - tree isomorphism-ish queries and "is u within distance K of v" reduce to two lifts.
Both phases visible: the depth-equalising lifts, then the pairs of jumps that stop one level below the answer. Toggle u and v to find a case where phase 2 does nothing.
q ≥ 106 with a tight time limit: O(log n) per query is 2 × 107 random memory reads across a 14 MB table — cache-hostile. Euler+RMQ with O(1) queries (LCA via Range Minimum Query) is faster there; Tarjan offline (Tarjan's Offline LCA) is faster still when updates do not exist. Also: if the tree is a path, lifting degenerates to depth arithmetic — just use an array.