Centroid decomposition builds a "centroid tree":
Find centroid of current tree
Make the root of current subtree in centroid tree
Mark as removed
For each component after removing , recursively decompose and attach as children of The centroid tree has depth. Every node in the original tree appears exactly once. The path from any node to the centroid tree root has length . This structure enables efficient queries: to answer a query about node , walk up the centroid tree from , processing each ancestor.