Introduction to Centroid Decomposition

You need to count paths in a tree, or find the closest node with property X from every vertex. Naive approaches are $O(n^2)$. The tree has $n$ nodes and you're checking all pairs. Too slow.

Centroid decomposition gives you $O(n \log n)$. Find the centroid (a node whose removal leaves no subtree larger than $n/2$), solve for paths through it, then recurse on subtrees. The recursion depth is $O(\log n)$.

I'll show you how to find centroids and apply this divide-and-conquer pattern.