Data Structures19 sections · 729 units
Open in Course

Building Heavy Chains

DFS construction

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:

  • chainHead[v]chainHead[v] = the top node of vv's chain
  • pos[v]pos[v] = position in the segment tree array
  • depth[v]depth[v] = depth in tree (for LCA)
  • parent[v]parent[v] = parent node

Nodes in the same chain get consecutive positions, enabling range queries.