GTOIgraph theory, redesigned

Chapter 10 · Lowest Common Ancestor

LCA by Heavy-Light Decomposition

Climbing chains instead of bits — same asymptotics, half the memory, and the same code you need for path queries.

  • hard
  • time n pre, log n query
  • space n
  • 1 snippet
  • hld
  • queries
  • trees
Read first
Definition

Decompose the tree into vertex-disjoint heavy paths (each vertex continues the path of its largest-subtree child, Heavy-Light Decomposition), and store for each vertex its chain's head h[v] and depth. Then:

cpphld-lca.cpp
int lca(int u, int v) {
    while (h[u] != h[v]) {
        if (depth[h[u]] < depth[h[v]]) swap(u, v);
        u = parent[h[u]];           // jump whole chains, always the deeper head
    }
    return depth[u] < depth[v] ? u : v;
}
TheoremO(log n) chains, without a log-size table

Each time the loop replaces u by parent(h[u]), the subtree of the new u has size at least twice the subtree of the old u's chain head: h[u] was a light child of its parent, and a light child has size ≤ half its parent's. Hence at most log2 n chain jumps.

Proof

size(h[u]) ≤ tfrac12 size(parent(h[u])) because the parent's heavy child has the largest subtree, so any light child carries at most half of the parent's vertices (the parent itself is the remainder, making it strictly less than half + 1). Composing along the loop gives size ≥ 2#jumps, so the count is at most log2 n. Termination is clear (heads strictly ascend), and correctness is the invariant "the LCA is an ancestor of both current vertices": the deeper head cannot be above the LCA (an ancestor of u that is deeper than lca is strictly below it), so jumping it is safe. ∎

Binary lifting vs. chain climbing

  • Memory: O(n) vs O(n log n) — one array per vertex vs 20, the reason to prefer HLD when n = 106 and memory is tight;
  • Speed: the loop usually runs 1–3 iterations on real trees (the log n bound is worst case), so it is faster than lifting for random trees and slower on adversarial "all-light" ones;
  • What lifting does that this cannot: k-th ancestor, "jump j steps", max-edge-on-path without a segment tree, functional graphs. Chain heads give you "the head" but not "the j-th up";
  • What HLD does that lifting cannot: path aggregates with point updates (the chains are contiguous in pos, so a segment tree over them answers sum/max/min on a path), and subtree updates with lazy propagation;
  • Preprocess: one DFS + one loop, both O(n) — no table build, so HLD's total setup is linear vs nlog n.
NoteSo which one?

If the problem is only LCA: binary lifting (shorter, self-contained, gives you lift). If it is LCA plus anything on paths: HLD, and use its lca as a by-product — writing both is 10 wasted lines. The hybrid "heavy-light + lifting on the chain forest" exists (jump between chains with lifting) but almost never wins in contests.

ExerciseTwo small exercises
  1. Modify lca above to return dist(u,v) in the same loop, using an additional wsum[v] = root-distance: which comparisons change?
  2. Show that "climb the deeper head" can be replaced by "climb the head with larger pos" only if the HLD numbering assigns pos in DFS order along chains. Find a tree where the naive pos comparison is wrong.