Graph Theory37 sections · 1633 units
Open in Course

Heavy and Light Edges

(Splitting by subtree size)

For each node vv with children, pick the child uu with the largest size[u]. The edge from vv to uu is heavy. All other edges from vv are light. If there is a tie for largest child, pick any one arbitrarily. Leaf nodes have no children, so no edges from them need classification.

This simple rule guarantees the O(log⁡n)O(\log n) chain property. Every node has at most one heavy edge going down to a child. A node can have multiple light edges down, but only one heavy edge.

Space complexity is O(n)O(n) for the data structures used.