시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 2 | 2 | 2 | 100.000% |
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 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.
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