Codeforces Problem 161D

For the standard tree-distance-k problem, root the tree and DFS. At node u, maintain counts of already processed descendant nodes by their distance from u. When processing child v, its count[v][d] represents nodes at distance d + 1 from u. Pair each such distance with previously accumulated distance k - (d + 1) to add exactly the pairs whose path passes through u; then merge the child's shifted counts. Initialize count[u][0] = 1. Processing children one at a time is what prevents double counting. Be precise about whether k is edges and validate k = 0 and a chain-shaped tree. With an O(k) vector per node/merge, the usual bound is O(nk) time and O(nk) memory, reducible with careful storage.