Module Heavy-light decomposition

Heavy-light decomposition

**Frequency: 2/10** ~~A wise man once said, if a data structure problem is not challenging enough, then throw it onto a tree.~~ HLD can be used to solve problems involving query on a path, enabling the use of some data structures like Segment Tree or BIT on the path.

Resources

- [CP Algorithms: Heavy-light decomposition](https://cp-algorithms.com/graph/hld.html)

Problems

Path queries 102 / 105 1800
Packages 65 / 75 1900
Greatest subarray sum on tree 51 / 64 2000
Chongqing Megacity 8 / 8 2000