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(logn)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.