Algorithm - Count Paths Through Centroid

$1.$ Find centroid $c$ of the current tree using the algorithm from the previous problem.

$2.$ DFS from $c$ to get distances to all nodes. Count pairs with distance sum $k$ using a frequency map.

$3.$ For each child subtree, DFS again and subtract pairs where both nodes are in that subtree.

$4.$ Remove $c$ and recursively process each component.

Time: $O(n \log n)$ because each node is processed $O(\log n)$ times and each processing is $O(1)$ or $O(\log n)$.

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