Description

有一棵有根树，包含 $n$ 个顶点，根顶点是 $1$。每个顶点上都有一个怪物。第 $i$ 个顶点上的怪物的生命值为 $hp_i$。

Kotori 想要消灭所有的怪物。第 $i$ 个顶点上的怪物可以被消灭，当且仅当其直接父节点上的怪物已经被消灭。消灭第 $i$ 个怪物所需的力量是 $hp_i$ 加上所有其他活着的怪物的生命值，这些怪物位于以 $i$ 为直接父节点的顶点 $j$ 上。形式化地，所需的力量等于

$$hp_i + \sum_{\begin{array}{c}\text{顶点 } j \text{ 上的怪物是\textbf{活着的}} \\ \text{且 } i \text{ 是 } j \text{ 的直接父节点} \end{array}} hp_j$$

此外，Kotori 可以使用一些魔法咒语。如果她使用一个魔法咒语，她可以在没有任何限制的情况下使用 $0$ 力量消灭任何怪物。也就是说，她可以选择一个怪物，即使其直接父节点上的怪物还活着。

对于每一个 $m=0,1,2,\cdots,n$，Kotori 想要分别知道如果她可以使用 $m$ 个魔法咒语，消灭所有怪物所需的最小总力量。

Input Format

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($2 \le n \le 2 \times 10^3$)，表示顶点的数量。

第二行包含 $(n-1)$ 个整数 $p_2,p_3,\cdots,p_n$ ($1 \le p_i < i$)，其中 $p_i$ 表示顶点 $i$ 的直接父节点。

第三行包含 $n$ 个整数 $hp_1,hp_2,\cdots,hp_n$ ($1 \le hp_i \le 10^9$)，表示每个怪物的生命值。

保证所有测试用例的 $n$ 的总和不超过 $2 \times 10^3$。

Output Format

对于每个测试用例，输出一行包含 $(n+1)$ 个整数 $a_0, a_1, \cdots, a_n$，用空格分隔，其中 $a_m$ 表示如果 Kotori 可以使用 $m$ 个魔法咒语，消灭所有怪物所需的最小总力量。

请不要在每行的末尾输出多余的空格，否则你的答案可能会被判为不正确！

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

Hint

题面翻译由 ChatGPT-4o 提供。