All submissions for this problem are available.
Let Lx denote the level of a node x in a rooted tree. Lx is 1 if x is the root, otherwise Lx = 1 + Ly, where y is the parent of x in the rooted tree. You need to calculate the sum Lx^K for all nodes x in the tree.
The first line contains the number of test cases T. T test cases follow. The first line of each test case contains N and K, where N is the number of nodes in the tree. 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 N lines for each test case. The ith line should contain the required sum if the tree is rooted at node i. Output all values modulo 1000000007. Output a blank line after each test case.
Input 2 3 2 0 1 1 2 3 3 0 1 0 2 Output 14 9 14 17 36 36
|Time Limit:||1.13473 - 1.67282 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, PYTH 3.6, PYPY, GO, NODEJS, rust, swift, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.