Complexity Analysis

Finding a centroid takes $O(n)$ time for a tree with $n$ nodes. The recursion has $O(\log n)$ depth because each level halves component sizes. Each node appears in $O(\log n)$ recursive calls. Processing paths through a centroid takes $O(n)$ time for that subtree.

Since each node is processed $O(\log n)$ times across all levels, total time is $O(n \log n)$. Overall: $O(n \log n)$ for building the decomposition and solving path problems. Space is $O(n)$ for the tree and auxiliary arrays.

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