← 返回题目列表

AtCoder · tkppc6_1_m

M. 致 LCA

中文机器翻译题面 查看原题

配点 : 600 点

問題文

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 Toshi 和碎片 q 所在的顶点 v 。一块 p ,顶点 移至 u 和 按字典顺序比较 v 最近的共同祖先。

完成所有操作后, 比方说 i 所在的顶点 t_i 。此时的比分是 \sum_{i=1}^{M} A_{t_i} 。找出最高分。

什么是最近共同祖先 (LCA)?

頂点 u 和 按字典顺序比较 v 的最近共同祖先是根(在这个问题中,顶点 与 1距离最远的顶点。两个顶点的最近共同祖先始终被确定为一个。

注意顶点 x 的祖先是顶点 从 x 开始并重复移动到父顶点可以到达的顶点(x 包括其本身)。

制約

  • 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)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
P_2 P_3 \ldots P_N
A_1 A_2 \ldots A_N
M
V_1 V_2 \ldots V_M

出力

最高分 1 行输出。


入力例 1

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

出力例 1

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 。


入力例 2

3
1 1
1 100 100
4
2 3 3 2

出力例 2

400

最好根本不要操作它。请注意,同一顶点上可以放置多个棋子。


入力例 3

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

出力例 3

40

原案: 森林