Chapter 10 · Lowest Common Ancestor
Tarjan's Offline LCA
Answer all LCA queries in near-linear time with a DFS and a disjoint-set union — no log factor, no table.
"All queries are known in advance and may be reordered." That licence is what makes this algorithm possible — and what makes it useless when a query depends on an earlier answer, or when vertices are added one by one.
Run a DFS. When a vertex v finishes, mark it black and union it with each black child, setting the child set's representative to v. For every query (v, u) with u already black, the answer is find(u).
When v is finishing and u is black, u lies entirely inside the finished part of the tree, and the union chain has pulled every black vertex whose "first not-yet-finished ancestor" is a = lca(u,v) into a's set: a vertex is unioned upward exactly when its own DFS finishes, so it stops at the highest ancestor that is still open — and a is still open (it is an ancestor of v), while everything on the u path below a is closed. No vertex outside a's subtree is in the set, since such a vertex would have had to be unioned through an ancestor of a, which is not yet finished. So find(u) = a. ∎
vector<vector<pair<int,int>>> adj(n); // neighbours, tree
vector<vector<pair<int,int>>> qs(n); // qs[v] = {(other, query id)}
vector<int> dsu(n), anc(n), state(n); // state: 0 white, 1 grey, 2 black
vector<int> ans(q);
int find(int v) { return dsu[v] == v ? v : dsu[v] = find(dsu[v]); }
void dfs(int v) {
state[v] = 1; anc[v] = dsu[v] = v;
for (int to : adj[v]) if (state[to] == 0) {
dfs(to);
dsu[find(to)] = v; anc[find(v)] = v; // pull the child set up to v
}
state[v] = 2; // black
for (auto [to, id] : qs[v])
if (state[to] == 2) ans[id] = anc[find(to)];
}anc[find(v)] = v; must be written after dsu[find(to)] = v;, and it must use find(v) — the representative after the merge. The anc array is the actual answer payload: dsu alone only tracks sets, and find returns an arbitrary member. Forgetting the anc update gives answers that are correct on stars and wrong on paths, which is the worst kind of bug.
Complexity and why it is near-linear
- O(n + q) DFS work plus O((n+q) α(n)) for the find calls: each tree edge causes one union, each query causes at most two finds,
- with union by size/rank the inverse-Ackermann factor is a constant ≤ 4 for any real n,
- memory O(n + q): no log n table (compare LCA by Binary Lifting's n log n),
- stack depth n: iterative version or
pthreadfor n = 106 (Walks, Trails, Paths, Cycles).
"n,q ≤ 2× 106", memory 64 MB, and each query is dist(u,v). Binary lifting needs 2× 106 × 21 × 4 B = 168 MB — over the limit. Tarjan needs dsu + anc + state + depth + tin ≈ 40 MB and answers all queries in one pass. This is not hypothetical: it is the standard intended difference on such problems, and the offline constraint is forced on you by memory, not stated in the problem.
The pattern "answer queries at the moment a vertex finishes, using the DSU state of closed subtrees" is Tarjan's offline framework, and it also solves: closest-pair-of-marked-nodes per subtree, "for each query vertex, the nearest ancestor satisfying P" (with a stack instead of DSU), and the offline version of "smallest subtree containing all query vertices" (Virtual Trees). Whenever a query's answer is determined by an ancestor relationship and everything relevant is already closed, offline DSU beats any table.