Chain Decomposition DFS

Run a DFS that assigns each node to a chain. Keep a counter $chain\_id$ that increments each time you start a new chain. At each node $v$, if $v$ is the start of a chain (no heavy edge from parent, or $v$ is root), assign chain[v] = chain_id and increment $chain\_id$.

Then recurse on the heavy child first with the same chain ID, then on light children with new chain IDs. This takes $O(n)$ time and labels every node with its chain. The heavy child continues the parent's chain. Light children start new chains.

Space complexity is $O(n)$ for the data structures used.