Single Segment Tree Improvement

Instead of separate segment trees for each chain, use one segment tree of size $n$. Assign each node a global position flat_pos[v]. During decomposition, maintain a global counter. Nodes in the same chain get consecutive positions. This way, chain $c$ occupying positions $l$ to $r$ maps directly to range $[l, r]$ in the single segment tree.

This simplifies implementation. You only manage one segment tree instead of many. Space usage drops from $O(n \log n)$ to $O(n)$. Most implementations use this improvement.

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