Problems
Counting on Tree
Counting on Tree
You are given a tree consisting of n nodes, each node i has a value ai
(0 ≤ ai
≤ 1) associated with it.
We call a set S of tree nodes beautiful if following conditions are satisfied:
- S is non-empty.
- S is connected. In other words, if nodes u and v are in S, then all nodes lying on the simple path between u and v should also be presented in S.
- Sum of all
au
(u belong to S) equals to k where k is a given integer.
Your task is to count the number of beautiful sets. Since the answer may very large, you should print it modulo 109
+ 7.
Input
The first line contains the number of test cases t. Then t test cases follow. Each test case consists of several lines:
- The first line contains two integers n (1 ≤ n ≤ 50000) and k (1 ≤ k ≤ 100).
- The second line contains n integers
a1
,a2
, ...,an
. - 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.
Output
For each test case print the answer in one line.
Input example #1
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 example #1
3 5 1