몬스터 헌터

정점이 $n$개인 루트 트리가 있고 루트 정점은 $1$번이다. 각 정점에는 몬스터가 한 마리씩 있다. $i$번 정점에 있는 몬스터의 체력은 $hp\_i$이다.

Kotori는 모든 몬스터를 죽이려고 한다. $i$번 정점의 몬스터는 $i$번 정점의 부모 정점에 있는 몬스터가 이미 죽어 있을 때만 죽일 수 있다. $i$번째 몬스터를 죽이는 데 필요한 힘은 $hp\_i$와, 부모 정점이 $i$번 정점인 정점 $j$에 살아 있는 다른 모든 몬스터의 체력의 합이다. 정확히 말해 힘은 다음과 같다. $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는 마법을 사용할 수 있다. 마법을 한 번 사용하면 아무 제약 없이 아무 몬스터나 0의 힘으로 죽일 수 있다. 즉, 부모 정점의 몬스터가 살아 있어도 그 몬스터를 고를 수 있다.

각 $m=0,1,2,\cdots,n$에 대해, 마법을 $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$번 사용할 수 있을 때 모든 몬스터를 죽이는 데 필요한 최소 총 힘이다.