Solution:
Use the node 0 as the root of tree. For each node, calculate the total number of children nodes (include itself) by DFS. Denote by "count".
For k=0. It's obviously. Just not pass through the root of tree. So the result is: $\sum_{child}{C_{child.count}^2}$.
If k=1. So it must pass through the root of tree, and not pass-through node 1. So just pick one node from any side. And pair it with any other nodes.
For other cases, and for any k. The shortest path of u and v must cover all nodes from 0 to k-1. So, once there is a branch between 0 and k-1, then all the subsequent k's result is 0.
So, after node 0 and node 1, We can get a list (at beginning, the list only has node 0 and node 1). Let us keep track the two ends of this list. For each k, we can choose one point from both ends.
Code:
Java
C++
