Reveal - Fixed-Length Paths I

Centroid Decomposition splits the tree recursively. At each step, find the centroid (the node whose removal leaves no subtree larger than $n/2$). Count all paths passing through the centroid.

For this problem: count pairs of nodes (one in each subtree of the centroid) whose combined distance to the centroid equals k. Use a frequency map to do this in linear time per level.

Then remove the centroid and recurse on each subtree. There are $O(\log n)$ levels, each doing $O(n)$ work, giving $O(n \log n)$ total.

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