Heavy Paths
Heavy-light decomposition, or HLD, divides a rooted tree into chains. Its main property is that any path between two vertices passes through only chains. This lets us process a tree path as a small number of array intervals.
We work with a tree whose edges do not change.
Let be the number of vertices in the subtree of , including itself:
A leaf has subtree size . For any other vertex, we add the sizes of its children's subtrees and then count the vertex itself. A DFS computes these sizes by processing the children before their parent.
At each vertex that has children, choose a child with the largest subtree.
If several children share the largest subtree size, we may choose any one of them. In our example, we break ties by choosing the smaller vertex number.
The tree below is rooted at vertex . Each circle shows the vertex number and its subtree size.
The choice depends on subtree sizes, regardless of the values stored at the vertices.
A heavy chain, also called a heavy path, is a path of heavy edges that cannot be extended by another heavy edge at either end. A vertex with no heavy edge incident to it forms a chain by itself.
Heavy edges cannot branch: each vertex has at most one heavy child and one parent. As a result, every vertex belongs to exactly one chain.
The topmost vertex of a chain, closest to the root, is its head. A chain starts at the root or at a vertex whose edge from its parent is light.
Our example has five chains. The head of each chain is filled blue.
Moving along a heavy edge keeps us in the same chain. Crossing a light edge takes us to another chain.
The numbers are always equal under our definition.
Every non-leaf vertex has a heavy child, so a heavy chain can end only at a leaf. Conversely, every leaf is the endpoint of exactly one chain, because each vertex belongs to exactly one chain.
Thus, pairing each chain with its final leaf gives a one-to-one correspondence. Changing a tie may move vertices between chains, but it cannot change the number of leaves or the total number of chains.
Suppose is a light child of . Its subtree contains fewer than half the vertices in the subtree of : .
To see why, let be the heavy child of . The subtree of is at least as large as the subtree of . These two disjoint subtrees, together with itself, all fit inside the subtree of .
Since is the heavy child, . Counting the parent and the two child subtrees gives
Therefore, .
Now follow a path from the root to any vertex. The root's subtree has size . Every time we descend along a light edge, the current subtree size becomes less than half as large.
After light edges, the current subtree has size at most . Since it must contain at least one vertex, .
Each light edge starts a new chain. Therefore, a root-to-vertex path touches at most chains.
The number of heavy edges along the path does not affect this count: consecutive heavy edges stay inside one chain.
The size guarantee applies to light children. A heavy child is simply a child with the largest subtree; it does not have to contain half of its parent's subtree.
The size bound can fail. Consider this tree:
The subtree of vertex is the path , so it has size and height . The subtree of vertex has four leaf children, so it has size and height . Here, height means the largest number of edges from the subtree's root to one of its descendants.
Choosing by height makes the heavy child of . The edge to would then be light, even though .
The original rule chooses . The halving proof needs a sibling with at least as many vertices as the light child's subtree; a taller sibling does not guarantee that.
Let be the lowest common ancestor of and : the deepest vertex that is an ancestor of both.
The path from to goes upward from to , then downward from to . Each part lies on a root-to-vertex path, so each crosses only light edges. The whole path therefore consists of chain portions.
Within each chain, the path uses a consecutive portion. It cannot leave a chain and later re-enter it, because that would give two different routes between vertices in a tree.
The path from to is highlighted below. Dashed blue edges separate the chain portions.
In path order, the three portions are , , and .
The light edges between and , and between and , separate these portions. Each path vertex appears exactly once.
A portion may use only part of its chain. Here, vertices and belong to the same chain as and , but they are outside the query path.
Eight vertices are not enough. The minimum is .
Work backward from the endpoint. Its subtree contains at least vertex. At every light edge, the parent must contain the light child's subtree, a heavy child's subtree of at least the same size, and the parent itself.
If the light child's subtree has at least vertices, its parent therefore has at least . Working upward across the three light edges gives minimum subtree sizes , then , then , then . Any heavy edges between them can only increase the required sizes.
To achieve , use a complete binary tree with four levels. The two child subtrees at each internal vertex have equal sizes, so we may choose every left child as heavy:
Every edge on goes to a right child and is light. The path therefore crosses exactly three light edges.
The earlier logarithmic bound is valid, but it is not always tight for a particular value of . Proving a lower bound and giving a matching construction identifies the exact minimum here.
When we assign consecutive array positions to the vertices of each chain, every chain portion becomes one array interval.
A tree path then becomes intervals. For a path-maximum query, we find the maximum on each interval and combine the results. With a segment tree, each interval query takes time, giving time for the full path query.
The next lesson shows how to assign these positions and find the intervals using chain heads.
Our example has five leaves and five heavy chains. Is this a coincidence, or must the number of chains always equal the number of leaves? Prove your claim or find a counterexample. Could changing how ties are broken change the total number of chains?
A student proposes choosing the child whose subtree has the greatest height instead of the greatest size. Would every light child still contain fewer than half of its parent's subtree vertices? Construct a counterexample with no tie in height, or explain why one cannot exist.
The bound does not rule out three light edges in a tree with vertices. Can a root-to-vertex path in such a tree actually cross three light edges? Find the smallest tree that can, and justify both why fewer vertices are impossible and why your construction works.