Round-Robin Tree

You are given a rooted tree with $N$ vertices. Vertex $1$ is the root.

For every non-leaf vertex $v$, you may choose one linear ordering of the children of $v$. The order is fixed before any ball is inserted and cannot be changed while the balls move.

Balls are inserted into the root one by one. Consider the $i$-th ball that enters a vertex $v$. If $v$ has $d_v$ children, the ball moves to the

-th child in the chosen order. A ball stops when it reaches a leaf.

Whenever a ball reaches a leaf $v$, you gain $C_v$ points. The value $C_v$ may be negative.

For every $x=1,2,\cdots,X$, find the maximum total score obtainable after inserting $x$ balls into the root. The child orderings may be chosen differently for different values of $x$.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ X$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_{N-1}\ v_{N-1}$ $C_1\ C_2\ \cdots\ C_N$

For every $i$, there is an edge between vertices $u_i$ and $v_i$. The given graph is a tree rooted at vertex $1$.

The values $C_i$ of non-leaf vertices do not affect the answer.

For each test case, print $X$ integers $A_1,A_2,\cdots,A_X$ on one line, separated by spaces.

$A_x$ must be the maximum total score obtainable after inserting $x$ balls into the root.

• $1 \le T \le 200\,000$.
• $1 \le N \le 200\,000$.
• $1 \le X \le 200\,000$.
• $1 \le u_i,v_i \le N$ ($1 \le i \le N-1$).
• $u_i \neq v_i$ ($1 \le i \le N-1$).
• The given edges form a tree.
• $-10^9 \le C_i \le 10^9$ ($1 \le i \le N$).
• The sum of $N$ over all test cases does not exceed $200\,000$.
• The sum of $X$ over all test cases does not exceed $200\,000$.