Counting on Tree#431
You are given a tree with nodes. Each node has an associated value a_i (0 \leq a_i \leq 1).
A set of nodes is called beautiful if it satisfies the following conditions:
is non-empty.
is connected. That is, if nodes and are in , then all nodes on the simple path between and are also in .
The sum of all a_u for u \in S is equal to , where is a given integer.
You need to count the number of beautiful sets. As this number may be large, print the answer modulo 10^9 + 7.
The first line contains the number of tests . Each test consists of the following lines:
The first line contains two integers (1 \leq n \leq 50000) and (1 \leq k \leq 100).
The second line contains integers a_1, a_2, \ldots, a_n.
Each of the next n - 1 lines contains two integers and (1 \leq u, v \leq n) meaning there is an edge between and . It is guaranteed that these edges form a tree.
For each test, print the answer on a separate line.
Example 1