分数: 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