CNTTREE - Trees Again


Given a tree, you need to count how many subtrees with diameter <= K exist.

Input

The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N and K. The following N - 1 lines contain two integers ai and bi, indicating an edge between nodes ai and bi in the tree. There is a blank line after each test case.

Output

Output T lines, one corresponding to each test case, containing the required answer.

Example

Sample Input:
2
3 1
0 1
1 2

6 3
0 1
1 2
2 3
2 4
3 5

Sample Output:
5
23

Constraints

1 <= T <= 100
2 <= N <= 60
0 <= ai, bi < N
1 <= K <= N - 1


hide comments
masterchef2209: 2018-10-12 13:14:04

one hell of a question

Sumit Vohra: 2016-02-14 16:30:11

well ! Its a DP-Tree question copied from Codechef " https://www.codechef.com/problems/TREES/ "

xuhd: 2015-11-27 04:28:15

can you enumerate all the FIVE subtrees for the first test case?
how can a tree with 3 nodes has 5 possible subtree, which has at most 1 node??
---------------------------------------------

my fault, i misunderstood the diameter of a tree

Last edit: 2015-11-27 04:57:32
LeppyR64: 2010-09-28 07:06:29

For those who have difficulty, make sure you have the definition of subtree correct:
http://mathworld.wolfram.com/Subtree.html


Added by:Varun Jalan
Date:2010-09-12
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC VB.NET
Resource:own problem