問題文

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

$M$ 個の駒があります。駒には $1, 2, \ldots, M$ の番号がつけられています。駒 $i$ は現時点では頂点 $V_i$ に置かれています。

あなたは、次の操作を $0$ 回以上の任意の回数行えます。

• 二つの駒 $p$ と $q$ を選ぶ。駒 $p$ が置かれている頂点を $u$ とし、駒 $q$ が置かれている頂点を $v$ とする。駒 $p$ を、頂点 $u$ と $v$ の最近共通祖先に移動させる。

全ての操作を終えた後に駒 $i$ が置かれている頂点を $t_i$ とします。このときのスコアは $\sum_{i=1}^{M} A_{t_i}$ で定められます。スコアの最大値を求めてください。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq P_i \leq i - 1$ $(2 \leq i \leq N)$
• $1 \leq A_i \leq 10^9$ $(1 \leq i \leq N)$
• $2 \leq M \leq 2 \times 10^5$
• $1 \leq V_i \leq N$ $(1 \leq i \leq M)$
• 入力は全て整数

入力例 1Copy

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

出力例 1Copy

24

次のように操作するのが最善です。

1. 駒 $p$ として駒 $1$ を選び、駒 $q$ として駒 $2$ を選ぶ。駒 $1$ が頂点 $2$ から頂点 $1$ に移動する。
2. 駒 $p$ として駒 $2$ を選び、駒 $q$ として駒 $3$ を選ぶ。駒 $2$ が頂点 $4$ から頂点 $3$ に移動する。
3. 駒 $p$ として駒 $3$ を選び、駒 $q$ として駒 $2$ を選ぶ。駒 $3$ が頂点 $5$ から頂点 $3$ に移動する。

最終的に $\lbrace t_i \rbrace = (1, 3, 3)$ となるので、スコアは $6 + 9 + 9 = 24$ です。

入力例 2Copy

3
1 1
1 100 100
4
2 3 3 2

出力例 2Copy

400

一度も操作しないのが最善です。二つ以上の駒が同じ頂点に置かれていることもあることに注意してください。

入力例 3Copy

6
1 2 2 3 4
1 5 6 2 8 8
8
4 1 5 6 2 3 1 3

出力例 3Copy

40

原案: Forested