교육적인 트리 문제

$N$개의 정점을 가진 트리가 주어진다. 각 정점에는 $1$번부터 $N$번까지 번호가 중복 없이 주어지며, $1$번 정점은 트리의 루트이다.

$2$ 이상 $N$ 이하의 모든 정수 $i$에 대해서, $i$번 정점의 부모 정점은 $p_i$번 정점이다.

이 트리의 $i$번 정점에는 정수 $A_i$가 적혀 있다. 또한, $A_i \leq A_{p_i}$ 라는 특수한 성질을 만족한다. 우리는 이 트리에서 몇 개의 정점을 선택하여, 선택된 정점들에 적혀있는 정수들의 합을 최대화하고 싶다. 이때 선택된 모든 정점은 $1$번 정점이거나, 자신의 부모 정점 또한 선택되어 있어야 한다.

선택할 정점들의 수에 따라 문제의 정답을 구해보자.

첫째 줄에 정수 $N$이 주어진다. $(2 \leq N \leq 300\ 000)$

둘째 줄에 정수로 이루어진 수열 $p_2, p_3, \cdots, p_N$이 공백으로 구분되어 주어진다. $(1\leq p_i < i)$

셋째 줄에 정수로 이루어진 수열 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1\leq A_i \leq 10^9)$

첫째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에는 $i$개의 정점을 선택했을 때의 정답을 출력한다.