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?
|
|
LeppyR64:
2010-09-28 07:06:29
For those who have difficulty, make sure you have the definition of subtree correct:
|
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 |