Centroid Decomposition - Structure

Centroid decomposition builds a "centroid tree":

$1.$ Find centroid $c$ of current tree

$2.$ Make $c$ the root of current subtree in centroid tree

$3.$ Mark $c$ as removed

$4.$ For each component after removing $c$, recursively decompose and attach as children of $c$

The centroid tree has $O(\log n)$ depth. Every node in the original tree appears exactly once. The path from any node to the centroid tree root has length $O(\log n)$. This structure enables efficient queries: to answer a query about node $v$, walk up the centroid tree from $v$, processing each ancestor.