Build HLD with two DFS passes: First DFS: Compute subtree sizes and identify heavy children. Second DFS: Assign chain IDs and positions.
When entering a node, first visit its heavy child (to keep chains contiguous), then visit light children. Each node gets: - = the top node of 's chain - = position in the segment tree array - = depth in tree (for LCA) - = parent node Nodes in the same chain get consecutive positions, enabling range queries.