Heavy-Light Decomposition

Heavy-light decomposition allows us to find the sum, maximum and minimum of paths alongside a tree, and also make updates to nodes along paths.

Resources

• https://usaco.guide/plat/hld?lang=cpp

• https://codeforces.com/blog/entry/81317

• https://cp-algorithms.com/graph/hld.html

• A heavy child of a node is the child with the largest subtree size rooted at the child.

• A light child of a node is any child that is not a heavy child.

• A heavy edge connects a node to its heavy child.

• A light edge connects a node to any of its light children.

• A heavy path is the path formed by a collection heavy edges.

• A light path is the path formed by a collection light edges.

Related

• Centroid Decomposition