Monster Hunter

There is a rooted tree with $n$ vertices, and the root vertex is $1$. Each vertex holds a monster. The hit points of the monster in vertex $i$ are $hp\_i$.

Kotori wants to kill all the monsters. The monster in vertex $i$ can be killed only if the monster in the direct parent of vertex $i$ has already 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 that live in a vertex $j$ whose direct parent is $i$. Formally, the power equals $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$

Kotori can also use 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 its direct parent is alive.

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

The input consists of multiple test cases. The first line of input contains an integer $T$, the number of test cases. Each test case is as follows.

The first line contains an integer $n$ ($2 \le n \le 2 \times 10^3$), 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$ is 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$), the hit points of each monster.

The sum of $n$ over all test cases does 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 spaces, where $a\_m$ is the minimum total power needed to kill all the monsters if Kotori can use $m$ magic spells.