P9634 [ICPC 2020 Nanjing R] Monster Hunter

有一棵有根树，包含 $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$ 个魔法咒语，消灭所有怪物所需的最小总力量。

有多个测试用例。输入的第一行包含一个整数 $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$。

对于每个测试用例，输出一行包含 $(n+1)$ 个整数 $a_0, a_1, \cdots, a_n$，用空格分隔，其中 $a_m$ 表示如果 Kotori 可以使用 $m$ 个魔法咒语，消灭所有怪物所需的最小总力量。 请不要在每行的末尾输出多余的空格，否则你的答案可能会被判为不正确！

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