Sweet Sugar
本题没有可用的提交语言。
Description
Prof.Chen is practicing baking cakes now. In the garden of his big house, there is an ingredient tree with $n$ vertices, labeled by $1,2,\dots,n$. On the $i$-th vertex of the tree, there are $c_i$ sweet sugars.
A cake will consume exactly $k$ sweet sugars. Every time before baking a new cake, Prof.Chen will come to the garden, select a component (or the whole tree) of vertices from a tree, then cut the component down, and take all the sugars from it. When a component is cut down, the original tree may split into several disconnected new trees. Also, note that it is not a good idea to waste sugars, so Prof.Chen will always make sure there are exactly $k$ sugars in the selected component.
Prof.Chen wants to make as many cakes as possible. Please help Prof.Chen to determine how many cakes he can make.
The first line contains a single integer $t$ ($1 \leq t \leq 10^6$), the number of test cases. For each test case:
The first line contains two integers $n$ and $k$ ($1\leq n\leq 10^6$, $1\leq k\leq 2\cdot 10^6$), denoting the number of vertices and the number of sugars in each cake.
The next line contains $n$ integers $c_1,c_2,\dots,c_n$ ($0\leq c_i\leq 2$), denoting the number of sweet sugars on each vertex.
Each of the following $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i,v_i\leq n$, $u_i\neq v_i$), describing an undirected tree edge between the $u_i$-th vertex and the $v_i$-th vertex. It is guaranteed that the edges form a tree.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
For each test case, output a single line containing an integer, denoting the maximum number of cakes that Prof.Chen can make.
Input
The first line contains a single integer $t$ ($1 \leq t \leq 10^6$), the number of test cases. For each test case:
The first line contains two integers $n$ and $k$ ($1\leq n\leq 10^6$, $1\leq k\leq 2\cdot 10^6$), denoting the number of vertices and the number of sugars in each cake.
The next line contains $n$ integers $c_1,c_2,\dots,c_n$ ($0\leq c_i\leq 2$), denoting the number of sweet sugars on each vertex.
Each of the following $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i,v_i\leq n$, $u_i\neq v_i$), describing an undirected tree edge between the $u_i$-th vertex and the $v_i$-th vertex. It is guaranteed that the edges form a tree.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
Output
For each test case, output a single line containing an integer, denoting the maximum number of cakes that Prof.Chen can make.
4
7 5
1 2 1 2 2 1 2
1 2
2 3
3 4
3 5
5 6
5 7
2 2
1 0
1 2
1 1
1
1 2
1
2
0
1
0