Auto comment: topic has been updated by Pawan_Lahoti (previous revision, new revision, compare).

We are exploiting the fact that for any two nodes (u,v), the lca in their centroid tree divides it into two disjoint paths.

Thus when we find a centroid, we effectively want to calculate the summation of cnt_i[x] * cnt_j[y] where cnt_i denotes the cnt of depth = x in child i of centroid and x + y == k. Because of the above mentioned fact, we won't get any repetition.

Time complexity: for each layer of centroids , we will do O(N) operations and because the height of centroid tree is limited to log(N), Time Complexity will be O(Nlog(N)).