ZOJ Problem Set - 3863
Edward has a tree with n vertices conveniently labeled with 1,2,…,n.
Edward finds a pair of paths on the tree which share no more than k common vertices. Now Edward is interested in the number of such ordered pairs of paths.
Note that path from vertex a to b is the same as the path from vertex b to a. An ordered pair means (A, B) is different from (B, A) unless A is equal to B.
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers n, k (1 ≤ n, k ≤ 88888). Each of the following n - 1 lines contains two integers ai, bi, denoting an edge between vertices ai and bi (1 ≤ ai, bi ≤ n).
The sum of values n for all the test cases does not exceed 888888.
For each case, output a single integer denoting the number of ordered pairs of paths sharing no more than k vertices.
1 4 2 1 2 2 3 3 4
The number of path pairs that shares no common vertex is 30.
The number of path pairs that shares 1 common vertex is 44.
The number of path pairs that shares 2 common vertices is 19.
Author: LIN, Xi
Source: The 15th Zhejiang University Programming Contest