Heavy–Light Tree Decomposition

Worked Example

Consider a path from vertex 3 to 6 on a tree where weights are (v+1). Here is the sequence of jumps required to find the path segments and its weight constraints. This gives us concrete steps and exact numerical traces.

1. Start at vertex 3, which is in a chain with head 0. Its depth is 2, while vertex 6 is in a chain with head 6, depth 2.
2. Since depth[head[6]] >= depth[head[3]] is false, we jump from 6 to parent[head[6]] which is 2. The segment includes just vertex 6 (weight 7).
3. Next, vertex 3 is at head 0, and vertex 2 is at head 2. Jump from 2 to parent[head[2]] which is 0. The segment includes just vertex 2 (weight 3).
4. Now, vertex 3 and vertex 0 are in the same chain (head 0). The segment between them in the chain array includes 0, 1, 3. Their weights are 1, 2, 4.
5. The total sum of weights is 7 + 3 + (1 + 2 + 4) = 17. The maximum weight is 7.

Experiment

Use the interactive module to trace paths between different nodes and see how the linear array is queried in disjoint intervals.

1. Open the Interactive Module.
2. Change the From node.
3. Change the To node to observe how the path is broken into disjoint linear intervals.

Limitations

This visualization demonstrates the decomposition on a fixed static tree. Dynamic link-cut trees or heavier topology updates are not supported in this basic model. Additionally, the segment tree that normally backs the linear arrays is abstracted away into direct array queries for simplicity. The layout focuses on educational demonstration rather than raw speed.

References

These references provide detailed analysis of the Heavy Light Decomposition approach and advanced tree data structures.

• MIT 6.851 Advanced Data Structures