0009 - Educational 木DP Problem

Problem

問題文

根が頂点1の木が与えられ, 各頂点に数が書かれている.

根を始点とする木のパスを考え, パスに含まれる頂点に書かれた数の和を最大化したい, 可能な和の最大値を求めよ.

制約

  • $1\le N\le 10^5 $
  • $1\le a_i\le N$
  • $1\le b_i\le 10^9$
  • 与えられるグラフは頂点1を根とした木

入力

入力は以下の形式で標準入力より与えられる.

$N$
$a_1\ a_2\ \cdots\ a_{N-1}$
$b_1\ b_2\ \cdots\ b_{N-1}\ b_N$

入力の説明

1行目に頂点数Nが与えられる.

2行目に辺の情報が与えられる, 頂点$i+1$と頂点$a_i$が辺で結ばれる.

3行目に頂点の情報が与えられる, 頂点$i$には数$b_i$が書かれている.

出力

可能な和の最大値を1行に出力してください.

入出力例

入力例 1

3
1 1
1 2 3

出力例 1

 4 

入力例 2

10
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10

出力例

 55