All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
Chef likes to play with trees a lot, so his best friend Smurf has given him a tree T consisting of N nodes numbered from 1 to N.
Smurf asked him to count the number of ways to assign an integer in the range [1, M] to each of the nodes of the tree such that the absolute difference between the integers assigned to any pair of adjacent nodes is greater or equal than K (i. e ≥ K). Since this number can be huge, Chef only needs to find it modulo 109 + 7 (1000000007)
Of course this task is tough for our little chef and he cannot solve it without your help. Can you help him?
The first line of input contains a single integer t denoting the number of test cases.
The first line of each test case contains three space separated integers denoting N, M and K, denoting the number of nodes in the tree and the values of M and K respectively.
The following (N-1) lines of each test case contain two space separated integers u and v denoting that there is an edge between the nodes u and v.
For each test case, print the answer in a separate line.
- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 100
- 0 ≤ K ≤ 100
- 1 ≤ M ≤ 109
- Subtask 1 (20 pts) : 1 ≤ M ≤ 102
- Subtask 2 (30 pts) : 1 ≤ M ≤ 104
- Subtask 3 (50 pts) : 1 ≤ M ≤ 109
Input 3 2 2 0 1 2 3 3 2 1 3 1 2 3 3 1 1 2 2 3 Output 4 2 12
|Tags||dynamic-programming, implementation, ltime35, ma5termind, medium, memoization|
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.