## § 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.