Ayvanat and Ugly Tree
All submissions for this problem are available.
Tidu is very pr0, but he has one weakness: Trees (maybe because trees are big and he's a smoll boi) Formally, a tree is defined as a collection of N connected nodes with N-1 edges where there is only one path from a node u, to another node v. One day a friend of Tidu's, Ayvanat, had an ugly tree of N nodes. The tree was ugly because the sum of values of nodes in the tree was not equal to his favourite number: a given K. Each node in the tree had a value associated with it A[i], where A[i] is either 0 or 1. Ayvanat wants to make the tree beautiful by removing any number of nodes (and their edges) from the tree, such that the tree still remains connected. However, he immediately realises there might be too many ways to make a tree beautiful. Ayvanat asks Tidu for help since he's very pr0, but doesn't know of his weakness. Tidu turns to you for help. Your task is to count the number of ways to make the tree beautiful. Since the answer may very large, you should print it modulo 10^9 + 7.
The first line contains one integer T - the number of test cases. Then T test cases follow.
The first line of each test case contains 2 integers N and K.
The second line contains N integers a, a, ..., a[N].
Then the next N - 1 line each contain pair of integers u and v (1 ≤ u, v ≤ N) denoting that there is an edge between u and v. It is guaranteed that these edges form a tree.
For each test case, output a single line containing the answer, the number of ways to create a beautiful tree, modulo 10^9+7.
Let SN be the sum of N over all test cases
1 ≤ SN ≤ 50000
1 ≤ K ≤ 100
Subtask 1: SN <= 25
Subtask 2: SN <= 1000
Subtask 3: Original constraints
Input: 3 3 1 1 0 1 1 2 1 3 5 2 0 1 0 1 1 1 2 1 3 1 4 2 5 3 0 1 1 0 1 2 2 3 Output: 3 5 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.