Core idea 2 - Combining Subtree Paths

From centroid $c$, run DFS to find the distance from $c$ to every node in its subtree. Store these distances in an array or map. A path of length $k$ through $c$ consists of two parts: distance $d_1$ from $c$ to node $u$ and distance $d_2$ from $c$ to node $v$, where $d_1 + d_2 = k$. You are looking for pairs that sum to $k$.

For each distance $d$, count how many nodes are at distance $k - d$. Sum these counts. Use a frequency map for $O(1)$ lookup.