Rikka with Treasure

By coincidentally, Rikka found a treasure map. She wants to employ several expedition teams to help her find the treasure.

There are $n$ caves in the treasure maps and $n-1$ undirected roads between the caves. For each cave pair $(i,j)(i \neq j)$, it is guaranteed that there is exactly one simple path between them, and the distance $d(i,j)$ between these two caves is defined by the number of caves in this path.

For example, in the following treasure map, $d(1,3) = 3, d(2, 5) = 2$ and $d(1,4)=4$.



Some of the caves have depots near them. Each expedition team can explore all the caves on the path ($s_i$, $t_i$)($s_i$ may be equal to $t_i$) which satisfies there are depots near $s_i$, $t_i$, and $s_i,t_i$ are stipulated by Rikka. After the exploration, Rikka needs to pay $d(s_i,t_i) \times C$ dollars to this team.

Each cave has treasure in it and the treasure in the $i$th cave worths $a_i$ dollars. Rikka can get $i$th treasure if and only if there are at least one expedition teams which have explored $i$th cave.

For example, in the previous treasure map, if $a_i=i,C=1$, all caves have depots near them, Rikka employs two expedition teams and the first team explores path $(1,5)$, the second team explores $(2,3)$, then Rikka need pay $3$ dollars to the first team, $2$ dollars to the second team, and Rikka can get treasure $1,2,3,5$. So the Rikka's income will be $1+2+3+5-3-2=6$ dollars.

Now, for each $K$ from $1$ to $n$, Rikka wants to calculate the maximum possible income she can get if she employs at most $K$ expedition teams.

The first line contains a single integer $t(1 \leq t \leq 10^3)$, the number of the testcases.

For each testcase, the first line contains three integers $n,C(1 \leq n \leq 3000, 1 \leq C \leq 10^7)$.

The second line contains $n$ 01 integers $p_i$. $p_i=1$ if and only if there is a depot near the $i$th cave.

The third line contains $n$ integers $a_i(1 \leq a_i \leq 10^7)$, which describes the value of the treasure.

Then $n-1$ lines follow, each line contains two integers $u_i,v_i$, which describes one road in the map.

The input guarantees that there are at least one depots and there are at most $5$ testcases with $n > 200$.

For each testcase, output a single line with a $n$ integers, the maximum possible income Rikka can get if she employs at most $i$ expedition teams.

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

7 7 7 7 7
10 10 10 10 10
10 10 10 10 10
4 4 4 4 4
7 9 10 10 10

2018 Multi-University Training Contest 9