Centroid Decomposition

Centroid Decomposition is divide-and-conquer for trees.

Find the centroid (a node whose removal splits the tree into components of at most $n/2$ nodes), process paths through it, then recurse on each component.

The centroid always exists and you can find it in $O(n)$ time. Since each component has at most half the nodes, the recursion depth is $O(\log n)$.

This technique performs well on distance-related problems: counting pairs at distance $k$, finding the closest marked node, and similar queries. The trick is that any path either passes through the centroid or lies entirely within one subtree.