scratch
§ CP Trick: Heavy Light Decomposition Euler Tour Tree
created 2022-01-28
- 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.
❦