Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3863
Paths on the Tree

Time Limit: 6 Seconds      Memory Limit: 131072 KB

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, bin).

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.

Sample Input

4 2
1 2
2 3
3 4

Sample Output



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.

path A paths share 2 vertices with A total
1-2-3-4 1-2, 2-3, 3-4 3
1-2-3 1-2, 2-3, 2-3-4 3
2-3-4 1-2-3, 2-3, 3-4 3
1-2 1-2, 1-2-3, 1-2-3-4 3
2-3 1-2-3, 1-2-3-4, 2-3, 2-3-4 4
3-4 1-2-3-4, 2-3-4, 3-4 3

Author: LIN, Xi
Source: The 15th Zhejiang University Programming Contest
Submit    Status