Divide and Conquer on Trees

Find the centroid $c$. Solve the problem for paths passing through $c$. Remove $c$ and recursively solve for each component. Combine the results. This is the standard pattern for all centroid decomposition problems. The recursion depth is $O(\log n)$, and processing paths through each centroid takes $O(n)$ or $O(n \log n)$ depending on the problem.

The total time depends on what you do at each centroid. This pattern applies to path counting, distance queries, and weighted path problems. You will see it repeatedly in the problems below.

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