Problem - Fixed-Length Paths I

You are given a tree with $n$ nodes and an integer $k$. Count the number of paths with exactly $k$ edges. A path is any sequence of edges connecting two nodes. A brute-force approach checking all $O(n^2)$ paths is too slow for large $n$.

Centroid decomposition reduces this to $O(n \log n)$ by processing paths through centroids. Let me show you how to split this problem into manageable pieces using centroid decomposition.

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