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