Heavy Path Decomposition Deep Dive: the light-edge proof, LCA without tables, order-aware path folds, O(log n) static queries and dynamic DP with (max,+) matrices

Heavy children, chains and a common misstatement

Root the tree and let size(v) be the number of vertices in v's subtree. For each internal vertex, mark one child with the largest subtree as heavy; every other child edge is light. Heavy edges form chains, and because every internal vertex has exactly one heavy child, the chains partition all n vertices. Each chain is named by its topmost vertex, its head.

A common misstatement, repeated in many notes, says the heavy child is the one holding at least half of the subtree. That is a different rule, from Sleator and Tarjan's original analysis, under which a vertex may have no heavy child at all. In the largest-child version used in practice the heavy child can hold far less than half: a vertex with ten equal children has a heavy child with about a tenth of the subtree. The bound does not need the heavy child to be big. It needs every light child to be small.

Why a path crosses only O(log n) chains

Claim: any path from a vertex up to the root crosses at most floor(log2 n) light edges. Take a light edge from parent p to child c. The heavy child h of p has size(h) >= size(c), and both are inside p's subtree, so 2 size(c) <= size(c) + size(h) < size(p). So size(p) > 2 size(c): every time you climb a light edge, the subtree size more than doubles. Starting from size at least 1 and never exceeding n, you can double at most log2 n times.

A path between any two vertices u and v goes up from u to their lowest common ancestor and down to v, so it touches at most 2 floor(log2 n) + 1 chains. The bound is tight: in a perfect binary tree both children have equal size, one is light, and a leaf reached by always taking the light child is log2(n + 1) - 1 light edges from the root. On the other extreme, a path graph is one chain and every query touches exactly one.

Two practical consequences follow. If each chain segment costs O(log n) in a segment tree, a path query costs O(log^2 n) in the worst case, but on most real trees the number of chains crossed is far below the bound. And any data structure that pays O(1) per chain gives O(log n) path queries.

An iterative build, and LCA for free

Recursive DFS overflows the stack on a path-shaped tree of a million vertices, so build in three passes over a BFS order: sizes bottom-up, heavy children, then chains top-down. Within a chain positions are consecutive, which is all the path machinery needs.

def decompose(n, adj, root=0):
    parent, depth = [-1] * n, [0] * n
    order, seen = [root], [False] * n
    seen[root] = True
    for u in order:                         # BFS: parents before children
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v], depth[v] = u, depth[u] + 1
                order.append(v)
    size, heavy = [1] * n, [-1] * n
    for u in reversed(order):               # children before parents
        if parent[u] >= 0:
            size[parent[u]] += size[u]
    for u in order:
        best = 0
        for v in adj[u]:
            if v != parent[u] and size[v] > best:
                best, heavy[u] = size[v], v
    head, pos, nxt = [0] * n, [0] * n, 0
    for u in order:
        if parent[u] == -1 or heavy[parent[u]] != u:   # u starts a chain
            v = u
            while v != -1:
                head[v], pos[v] = u, nxt
                nxt += 1
                v = heavy[v]
    return parent, depth, heavy, head, pos

The decomposition alone answers lowest common ancestor queries in O(log n) with no extra memory: repeatedly lift whichever endpoint's chain head is deeper to the parent of that head; when both are on one chain, the shallower vertex is the LCA. Compared with binary lifting it uses O(n) instead of O(n log n) memory and touches fewer cache lines, which often makes it faster in practice.

Path aggregates where order matters

Sums and maxima do not care about direction. Many useful aggregates do: composing affine functions x -> ax + b along a route, concatenating labels, or a matrix product along a path. The upward part from u to the LCA must be read against the array order (positions increase going down a chain), and the downward part to v must be read with it, then appended in reverse order of discovery.

def path_segments(u, v, parent, depth, head, pos):
    # Position ranges covering the path u..v, split by side.
    up_u, up_v = [], []                     # up_u: walk high->low pos; up_v: low->high
    while head[u] != head[v]:
        if depth[head[u]] >= depth[head[v]]:
            up_u.append((pos[head[u]], pos[u])); u = parent[head[u]]
        else:
            up_v.append((pos[head[v]], pos[v])); v = parent[head[v]]
    if depth[u] >= depth[v]:
        up_u.append((pos[v], pos[u]))
    else:
        up_v.append((pos[u], pos[v]))
    return up_u, up_v

def path_fold(u, v, seg_rev, seg_fwd, op, identity, *dec):
    up_u, up_v = path_segments(u, v, *dec)
    left = identity
    for lo, hi in up_u:                     # in order of discovery, read upward
        left = op(left, seg_rev(lo, hi))
    right = identity
    for lo, hi in up_v:                     # discovered bottom-up, so prepend
        right = op(seg_fwd(lo, hi), right)
    return op(left, right)

Here dec is (parent, depth, head, pos) from the build, and seg_fwd(lo, hi) returns the aggregate of positions lo..hi in increasing order and seg_rev the same range in decreasing order, so the segment tree stores both directions in every node. Forgetting the reversed copy is the most common bug in this code, and it is invisible in tests that only use commutative operations.

When the cost drops to O(log n)

If values never change and the operation has an inverse, as sums and XOR do, store prefix sums over the position array. A chain segment then costs one subtraction, pref[hi + 1] - pref[lo], and a path query is O(log n) in total. There is a further shortcut: every segment except the one containing the LCA starts at a chain head, so static per-chain prefix maxima from the head cover all of them, and a sparse table answers the one remaining segment in O(1), giving O(log n) even for max.

With updates, the standard combination is one segment tree over all positions, at O(log^2 n) per path query. Asymptotically better designs exist, such as replacing the per-chain balanced trees with trees weighted by light-subtree sizes, which brings path operations to O(log n); they are worth it only when profiles show the log-squared term dominating.

Dynamic DP along chains

The most powerful use of chains is dynamic programming under updates. Take the maximum weight independent set on a tree, where vertex weights change. Let f0(v) and f1(v) be the best value in v's subtree with v excluded or included. Split each vertex's children into its heavy child h and the rest, and fold the light children into two numbers:

g0(v) = sum over light children c of max(f0(c), f1(c))
g1(v) = w(v) + sum over light children c of f0(c)

[f0(v)]   [ g0(v)  g0(v) ]   [f0(h)]        (max,+) product:
[f1(v)] = [ g1(v)  -inf  ] x [f1(h)]        (A x B)[i][j] = max_k A[i][k] + B[k][j]

The value at a chain head is the product of these 2x2 matrices along the chain, applied to the vector [0, -inf] below the chain's last vertex. Store the matrices in a segment tree over positions, so a chain product is a range query. When w(v) changes, update g1(v) and its leaf, recompute the head's (f0, f1), and push the difference into the parent of the head, which is a light-child contribution there. Repeat up through at most log n chains.

The trick generalises. Any tree DP whose dependence on the heavy child can be written as a matrix product in some semiring fits the same scheme: (max,+) for maximum-weight problems, (min,+) for minimum vertex cover or minimum-cost labelling, and ordinary (+,x) arithmetic for counting problems modulo a prime. The cost per update is O(log n) chains, each needing a point update and a range product of k x k matrices, so O(k^3 log^2 n) in total; with k = 2 that is a few dozen additions and comparisons per segment-tree node. Remember that (max,+) products are associative but not commutative, so the segment tree must multiply in position order, top of the chain on the left.

def update(self, u, new_w):
    self.g1[u] += new_w - self.w[u]; self.w[u] = new_w
    while u != -1:
        h = self.head[u]
        old = self.chain_f(h)               # (f0, f1) at the head before the change
        self.set_leaf(self.pos[u], self.mat(u))
        new = self.chain_f(h)
        p = self.parent[h]
        if p == -1:
            break
        self.g0[p] += max(new) - max(old)   # h is a light child of p
        self.g1[p] += new[0] - old[0]
        u = p

Worked example. Root 0 has children 1 and 2; vertex 1 has children 3 and 4; vertex 3 has child 5. Weights are 4, 5, 3, 6, 2, 7 for vertices 0 to 5. Sizes make chain 0-1-3-5 heavy, with 2 and 4 as single-vertex chains. Then g0(1) = max(0, 2) = 2, g1(1) = 5, g0(0) = 3 and g1(0) = 4. Folding up the chain: f(3) = (7, 6), f(1) = (2 + 7, 5 + 7) = (9, 12), f(0) = (3 + 12, 4 + 9) = (15, 13), so the answer is 15, from {1, 2, 5}. Now set w(4) = 10. Vertex 4's chain value moves from (0, 2) to (0, 10), so g0(1) rises by 8 to 10; f(1) = (17, 12), f(0) = (3 + 17, 4 + 17) = (20, 21), and the answer is 21, from {0, 4, 5}.

Failure modes

• Recursion depth. A recursive DFS crashes on deep trees; use the BFS build.
• Direction bugs. Non-commutative folds give wrong answers that commutative tests never reveal. Test with affine composition or string concatenation against a brute path walk.
• Edge values counted at the LCA. When values live on edges, store each at its child vertex and exclude the LCA's position from the final segment.
• Stale DDP contributions. Forgetting to subtract the head's old value from its parent's g double-counts after every update.
• Changing topology. The decomposition is computed once. If edges are added or cut, sizes and heavy children go stale and the bound no longer holds; use link-cut trees instead.

Trade-offs

Heavy path decomposition is the right default for a static tree with path queries and point or path updates: linear memory, simple arrays and a small constant. Binary lifting is simpler when you only need ancestors and LCA. Euler tours handle subtree queries alone with one range per vertex. Centroid decomposition fits distance-style questions such as nearest marked vertex. Link-cut trees handle a changing forest at the cost of amortised analysis and more complex code.

What to do next

1. Implement the BFS build and check the light-edge bound on random trees.
2. Add LCA by chain jumping and compare it with a naive parent walk on 10,000 random pairs.
3. Write path_fold with a segment tree storing both directions; test it with affine maps.
4. Use prefix sums for a static path-sum problem and confirm O(log n) chain counts.
5. Implement the (max,+) DDP for independent set and check every update against a full recompute.
6. Measure chains crossed per query on your real trees before optimising anything further.