← 返回题目列表

AtCoder · awc0011_d

D. 家谱和继承

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

分数: 366 分

问题陈述

高桥正在调查他家族的家谱。家庭成员包括 N 人,每人编号为 1 to N.

在这个家谱中,除了人之外的每个人 1作为始祖,只有一个“父母”。人的父母 i (2 \leq i \leq N) 是人 P_i。通过这些亲子关系,所有人与人结成了一棵有根的树 1 作为根。

对于每个人 i,值 记录该人留下的遗产的 V_i 。

高桥定义了一个人的“累积继承” X 作为来自人的路径上所有人的继承值的总和 X 致开国祖师(人 1),通过反复跟随父母(包括两人)获得 X 他们自己和人 1.

你被给予 Q 查询。对于每个查询,一个人员编号 已指定 X_j 。求该人的累计遗产数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_i < i (2 \leq i \leq N)
  • 1 \leq X_j \leq N (1 \leq j \leq Q)
  • 所有输入值均为整数

输入

输入由以下格式的标准输入给出。

N Q
V_1 V_2 \ldots V_N
P_2 P_3 \ldots P_N
X_1
X_2
\vdots
X_Q
  • 第一行包含人数 N 和查询数量 Q,用空格分隔。
  • 第二行包含继承值 每个人的 V_1, V_2, \ldots, V_N ,用空格分隔。
  • 第三行包含父编号 P_2, P_3, \ldots, P_N 对于人 2 通过 N,以空格分隔。当 N = 1,这一行是空的。
  • 以下各项 Q 行包含为每个查询指定的单个人员编号。具体来说, j这些行中的第 (1 \leq j \leq Q) 包含 X_j.

输出

输出 Q 行。上 j- 第行 (1 \leq j \leq Q),输出person的累计继承 X_j 中指定 j-第一个查询作为整数。

ans_1
ans_2
\vdots
ans_Q

示例输入 1

5 3
10 20 30 40 50
1 1 2 2
1
4
5

示例输出 1

10
70
80

示例输入 2

7 5
100 200 300 150 250 50 400
1 1 2 2 3 3
1
3
5
6
7

示例输出 2

100
400
550
450
800

示例输入 3

10 8
1000000000 500000000 300000000 200000000 100000000 800000000 600000000 400000000 250000000 150000000
1 1 2 2 3 3 4 5 6
1
4
7
8
9
10
3
6

示例输出 3

1000000000
1700000000
1900000000
2100000000
1850000000
2250000000
1300000000
2100000000