Centroid Decomposition is divide-and-conquer for trees.
Find the centroid (a node whose removal splits the tree into components of at most nodes), process paths through it, then recurse on each component.
The centroid always exists and you can find in time. Since each component has at most half the nodes, the recursion depth is .
This technique performs well at distance-related problems: counting pairs at distance , 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.