408125: GYM102992 M Monster Hunter

There is a rooted tree with $$$n$$$ vertices and the root vertex is $$$1$$$. In each vertex, there is a monster. The hit points of the monster in the $$$i$$$-th vertex is $$$hp_i$$$.

Kotori would like to kill all the monsters. The monster in the $$$i$$$-th vertex could be killed if the monster in the direct parent of the $$$i$$$-th vertex has been killed. The power needed to kill the $$$i$$$-th monster is the sum of $$$hp_i$$$ and the hit points of all other living monsters who lives in a vertex $$$j$$$ whose direct parent is $$$i$$$. Formally, the power equals to $$$$$$ hp_i + \sum_{\begin{array}{c}\text{the monster in vertex } j \text{ is \bf{alive}} \\ \text{and } i \text{ is the direct parent of } j \end{array}} hp_j $$$$$$

In addition, Kotori can use some magic spells. If she uses one magic spell, she can kill any monster using $$$0$$$ power without any restriction. That is, she can choose a monster even if the monster in the direct parent is alive.

For each $$$m=0,1,2,\cdots,n$$$, Kotori would like to know, respectively, the minimum total power needed to kill all the monsters if she can use $$$m$$$ magic spells.

There are multiple test cases. The first line of input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \times 10^3$$$), indicating the number of vertices.

The second line contains $$$(n-1)$$$ integers $$$p_2,p_3,\cdots,p_n$$$ ($$$1 \le p_i < i$$$), where $$$p_i$$$ means the direct parent of vertex $$$i$$$.

The third line contains $$$n$$$ integers $$$hp_1,hp_2,\cdots,hp_n$$$ ($$$1 \le hp_i \le 10^9$$$) indicating the hit points of each monster.

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$2 \times 10^3$$$.

For each test case output one line containing $$$(n+1)$$$ integers $$$a_0, a_1, \cdots, a_n$$$ separated by a space, where $$$a_m$$$ indicates the minimum total power needed to kill all the monsters if Kotori can use $$$m$$$ magic spells.

Please, DO NOT output extra spaces at the end of each line, otherwise your answer may be considered incorrect!

3
5
1 2 3 4
1 2 3 4 5
9
1 2 3 4 3 4 6 6
8 4 9 4 4 5 2 4 1
12
1 2 2 4 5 3 4 3 8 10 11
9 1 3 5 10 10 7 3 7 9 4 9

29 16 9 4 1 0
74 47 35 25 15 11 7 3 1 0
145 115 93 73 55 42 32 22 14 8 4 1 0