题目描述

有一个根为1的树，树上有$n$个顶点。每个顶点上都有一只怪物，第$i$个顶点上的怪物的血量是$hp_i$。

Kotori 想要杀死所有的怪物。第 $i$ 个顶点上的怪物可以被击败，前提是第 $i$ 个顶点的直接父节点上的怪物已经被击败。击败第 $i$ 个怪物所需的能量等于 $hp_i$ 加上所有其他活着的怪物的血量之和，这些怪物居住在一个顶点 $j$，而 $j$ 的直接父节点是$i$。具体来说，能量等于

$$hp_i + \sum_{\begin{array}{c}\text{顶点} j \text{中的怪物还 \bf{活着}} \\ \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$)，代表顶点$i$的直接父节点是$p_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$ 表示小鸟在可以使用 $m$ 次魔法时杀死所有怪物所需的最小总能量。

请注意，不要在每行末尾输出额外的空格，否则可能被判定为错误答案！