A balanced tree of centers
Centroid decomposition rebuilds a tree as a hierarchy of split points. A centroid of a tree is a node whose removal leaves every remaining piece at most half the size. Choosing centroids repeatedly creates a shallow structure of well balanced layers.
Building the decomposition
- Find the centroid of the current tree.
- Make it the root of this layer and remove it.
- Recurse on each resulting piece, attaching their centroids as children.
Because each split halves the largest part, the decomposition has only a logarithmic number of levels. Every original node appears once as a centroid, on exactly one level.
Why paths become easy
The decisive property is that every path in the original tree passes through the centroid of the smallest decomposition piece that contains both endpoints. So instead of looking at all paths, an algorithm can fix a centroid and consider only paths that go through it, then recurse. This turns many path counting and distance problems into manageable per centroid work across few levels.
Key idea
Recursively root the tree at balanced centroids so the structure stays shallow and every path crosses a centroid that owns it.