#411 Round-Robin Tree

Statement

정점이 $N$ 개인 루트 있는 트리가 주어진다. 루트는 $1$ 번 정점이다.

리프가 아닌 각 정점 $v$ 에 대해, $v$ 의 자식들을 한 줄로 나열한 순서를 하나 정할 수 있다. 이 순서는 공을 넣기 전에 정하며, 공이 이동하는 동안에는 바꿀 수 없다.

공을 루트에 하나씩 넣는다. 어떤 정점 $v$ 에 들어온 공 중 $i$ 번째 공을 생각하자. 정점 $v$ 의 자식 수를 $d_v$ 라 하면, 이 공은 정해 둔 순서에서

((i-1) \bmod d_v)+1

번째 자식으로 이동한다. 공은 리프에 도착하면 멈춘다.

공 하나가 리프 $v$ 에 도착할 때마다 $C_v$ 점을 얻는다. $C_v$ 는 음수일 수도 있다.

각 $x=1,2,\cdots,X$ 에 대해, 루트에 공을 $x$ 개 넣었을 때 얻을 수 있는 총점의 최댓값을 구하여라. 자식들의 순서는 $x$ 마다 서로 다르게 정해도 된다.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 $i$ 에 대해 $u_i$ 번 정점과 $v_i$ 번 정점을 잇는 간선이 있다. 주어진 그래프는 트리이다. 트리의 루트는 $1$ 번 정점이다.

리프가 아닌 정점의 $C_i$ 는 답에 영향을 주지 않는다.

각 테스트 케이스마다 한 줄에 $X$ 개의 정수 $A_1,A_2,\cdots,A_X$ 를 공백으로 구분하여 출력한다.

$A_x$ 는 루트에 공을 $x$ 개 넣었을 때 얻을 수 있는 총점의 최댓값이어야 한다.

Input

2
5
2
3
4
5
5 1 0 3
6
2
3
4
5
6
7
0 0 10 0 6 5

Output

5 8 9 14 17
10 16 21 21 31 37

각 $x$ 에 대해 자식 순서를 하나 정한 뒤 공의 이동을 규칙대로 진행하면 된다. 가장 높은 총점을 만드는 순서를 선택하면 출력과 같은 값을 얻는다.