
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. InputThere 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 a_{i}, b_{i}, denoting an edge between vertices a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n). The sum of values n for all the test cases does not exceed 888888. OutputFor each case, output a single integer denoting the number of ordered pairs of paths sharing no more than k vertices. Sample Input1 4 2 1 2 2 3 3 4 Sample Output93 HintThe 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 