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.
47 51 2 1 2 2 1 21 22 33 43 55 65 72 21 01 21 111 21
2 0 1 0
