시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 5 3 3 60.000%

문제

You have a rooted tree, some vertices have coins lying on them. 

You can do the following operation any number of times: take some two vertices $u$ and $v$, such that there are no coins at lowest common ancestor of $u$ and $v$ but both vertices $u$ and $v$ have non-zero amount of coins $a_u$ and $a_v$ and put $a_u + a_v$ coins at their lowest common ancestor.

Your goal is to maximize the sum of the number of coins on all vertices.

입력

The first line contains single integer $n$ ($2 \leq n \leq 10^5$) --- number of vertices of the tree.

The root of the tree is vertex $1$.

The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$, $p_i$ is the parent of vertex $i$ ($1 \le p_i < i$).

The third line contains $n$ integers $a_1, a_2, \ldots, a_n$, $a_i$ is the number of coins that lie on vertex $i$ ($0 \leq a_i \leq 10^5$).

출력

Print one integer --- the maximum total amount of coins that you can get by applying the described operations.

서브태스크

번호 배점 제한
1 5

$n \leq 5, a_i \leq 1$

2 5

$n \leq 20$

3 10

$n \leq 2000, a_i \leq 1$

4 20

$n \leq 2000$

5 20

$a_i \leq 1$

6 40

No additional constraints.

예제 입력 1

3
1 1
0 1 1

예제 출력 1

4

예제 입력 2

5
1 1 3 4
5 3 4 2 4

예제 출력 2

18

채점 및 기타 정보

  • 예제는 채점하지 않는다.