Divide and conquer on trees
Centroid decomposition breaks a tree into a hierarchy by repeatedly removing a special node called a centroid. It is the tree analogue of divide and conquer, and it is powerful for counting or answering queries about paths in a tree.
What a centroid is
A centroid of a tree is a node whose removal leaves every remaining piece with at most half the original nodes. Every tree has at least one. Because each split halves the size, the resulting centroid tree has only logarithmic depth.
Building the decomposition
- Find the centroid of the current tree.
- Make it the root of this part of the centroid tree, then remove it, splitting the tree into smaller subtrees.
- Recurse into each subtree, attaching its centroid as a child of the one just removed.
Because any path in the original tree passes through the centroid of some level, you can account for all paths by processing each centroid against the pieces hanging off it. The total work across all levels stays near the node count times a logarithm.
Key idea
Recursively rooting at a centroid halves the tree each step, giving a logarithmic depth hierarchy where every original path crosses some centroid.