問題一覧 > 通常問題

No.1524 Upward Mobility

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 14
作問者 : aspiaspi / テスター : 沙耶花沙耶花 NatsubiSoganNatsubiSogan NachiaNachia
0 ProblemId : 6204 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-21 00:18:31

問題文

頂点に $1$ から $N$ までの番号がついた、$N$ 頂点の根付き木が与えられます。根は頂点 $1$ で、頂点 $i\ (2 \leq i \leq N)$ の親は頂点 $p_i$ です。

この木の頂点 $i\ (1 \leq i \leq N)$ には、整数 $a_i,b_i$ が書かれています。

あなたは、$0$ 個以上の頂点を選んで、選んだ頂点に書かれている $a_i,b_i$ を両方消すことにしました。ただし、あなたは上昇志向が強いので、木の任意の葉 $v$ について以下の条件が満たされるようにしたいです。

  • 頂点 $1$ から頂点 $v$ に向かう単純パスを考える。
  • パス上の頂点に書かれている $a_i$ を($a_i$ が消されている頂点は無視して)パスに沿った順に並べたとき、これは単調増加になっている。

条件を満たしつつ、 $a_i,b_i$ を消す頂点を適切に選択したとき、残りの頂点に書かれている $b_i$ の総和は最大でいくつになるでしょうか。

入力

$N$
$p_2\ p_3\ \ldots \ p_N$
$a_1\ a_2\ \ldots \ a_N$
$b_1\ b_2\ \ldots \ b_N$
  • 入力はすべて整数
  • $2 \leq N \leq 10^5$
  • $1 \leq p_i < i$
  • $1 \leq a_i \leq N$
  • $a_1,a_2,\cdots,a_N$ は相異なる
  • $1 \leq b_i \leq 10^9$

出力

適切に頂点上の整数を削除したときの、$b_i$ の総和の最大値を $1$ 行に出力してください。

最後に改行してください。

サンプル

サンプル1
入力
6
1 1 2 3 2
5 3 6 2 4 1
2 1 8 7 8 5
出力
20

サンプル2
入力
10
1 1 3 2 4 1 6 8 6
1 3 6 7 5 10 2 9 8 4
18 93 98 53 42 34 61 73 91 42
出力
456

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。