§ CP trick: Heavy Light Decomposition euler tour tree
- To implement HLD, first define heavy edge to be edge to heaviest vertex.
- To use segment tree over HLD paths, create a "skewed" DFS where each node visits heavy node first, and writes vertices into an array by order of discovery time (left paren time).
- When implementing HLD, we can use this segment tree array of the HLD tree as an euler tour of the tree.
- We maintain intervals so it'll be
[left paren time, right paren time]. We find right paren time based on when we exit the DFS. The time we exit the DFS is the rightmost time that lives within this subtree.