Centroid Decomposition splits the tree recursively. At each step, find the centroid (the node whose removal leaves no subtree larger than ). 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 levels, each doing work, giving total.
Space complexity is for the data structures used.