Centroid Properties

Removing a centroid leaves components with at most $n/2$ nodes. This guarantees balanced splits, which means recursive depth is $O(\log n)$. Each level of recursion halves the problem size. Every path in the tree passes through some centroid in the decomposition. This is the core idea: process paths through centroids, not all paths directly.

You count paths at each centroid, avoiding $O(n^2)$ brute force. These properties turn $O(n^2)$ brute force into $O(n \log n)$ divide-and-conquer. The balance is what makes it work.

Space complexity is $O(n)$ for the data structures used.