問題文

N 頂点の根付き木があります。頂点には 1 から N までの番号がつけられています。この木の根は頂点 1 で、2\leq i\leq N について頂点 i の親は P_i\,(P_i\lt i) です。

あなたはこれから (1,2,\ldots,N) の順列 Q=(Q_1,Q_2,\ldots,Q_N) を 1 つ決めます。すると、各 1\leq i\leq N について、頂点 Q_i が頂点 V_i の部分木内にあるときにコスト C_i が発生します。

発生するコストの総和の最小値を計算してください。

制約

• 2\leq N\leq2\times10^5
• 1\leq P_i\lt i
• 1\leq V_i\leq N
• 1\leq C_i\leq10^9

入力例 1

3
1 2
2 2 2
1 2 3

出力例 1

3

Q=(3,2,1) とすると、発生するコストの総和は 1+2=3 です。これが最小値です。

入力例 2

5
1 1 1 1
1 2 3 4 5
5 4 3 2 1

出力例 2

5

入力例 3

9
1 2 3 2 3 2 3 2
2 2 2 3 3 2 3 2 3
124 981 554 92 498 327 613 709 192

出力例 3

1714