Dense Subgraph

You have a tree on $n$ vertices, and each vertex has a weight $a_v$ and a degree at most $5$.

Let's call the density of a subset of vertices $S$ value $\frac{\sum_{v \in S} a_v}{|S|}$, and call the beauty of the tree with some vertices turned off the maximum value of the density of a subset of at least two turned on vertices with connected induced subgraph, or $0$ if no such subset exists.

Now you need to calculate the number of ways to choose such a set of turned off vertices among $2^n$ ways that the beauty of the tree is no larger than $x$, modulo $1\,000\,000\,007$.

The input contains several test cases, and the first line contains a single integer $T~(1 \le T \le 30)$, the number of test cases.

The first line of each test case contains two integers $n~(2 \leq n \leq 35\,000)$ and $x~(0 \leq x \leq 35\,000)$, the number of vertices of a tree and the constraint on the beauty.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n~(0 \leq a_i \leq 35\,000)$, the weights of the tree vertices.

Each of the next $n-1$ lines contains two integers $u$ and $v~(1 \leq u, v \leq n)$, describing an edge connecting vertices $u$ and $v$ in the tree.

It is guaranteed that each vertex of a tree has a degree at most $5$.

For each test case, output a line containing a single integer, indicating the number of ways to choose such a set of turned off vertices among $2^n$ ways that the beauty of the tree is no larger than $x$, modulo $1\,000\,000\,007$.

2
5 0
1 1 1 1 1
1 2
2 3
3 4
4 5
3 2
2 1 3
1 2
1 3

13
6

2019 Multi-University Training Contest 10