You need to count paths in a tree, or find the closest node with property X from every vertex. Naive approaches are . The tree has nodes and you're checking all pairs. Too slow.
Centroid decomposition gives you . Find the centroid (a node whose removal leaves no subtree larger than ), solve for paths through it, then recurse on subtrees. The recursion depth is .
I'll show you how to find centroids and apply this divide-and-conquer pattern.
