Building the Decomposition Tree

Start with the full tree. Find its centroid $c$. Mark $c$ as processed. Split the tree into components by removing $c$. Recursively find centroids of each component. Store parent-child relationships in the decomposition tree. Each recursive call works on a tree with at most $n/2$ nodes.

The recursion depth is $O(\log n)$, and each level processes all $n$ nodes once. You recompute subtree sizes for each component. Total time: $O(n \log n)$. You rebuild size arrays for each component, but the halving keeps it logarithmic. Space is $O(n)$ for the tree structure.

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