D - Family Tree and Inheritance Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は自分の一族の家系図を調べています。一族には N 人の人物がおり、それぞれに 1 から N までの番号が付けられています。

この家系図において、一族の始祖である人物 1 を除くすべての人物には「親」が 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
  • 1 行目には、人物の数 N とクエリの数 Q が、スペース区切りで与えられる。
  • 2 行目には、各人物の遺産の価値 V_1, V_2, \ldots, V_N が、スペース区切りで与えられる。
  • 3 行目には、人物 2 から人物 N までの親の番号 P_2, P_3, \ldots, P_N が、スペース区切りで与えられる。ただし N = 1 のときは、この行には何も書かれていない（空行）。
  • 続く Q 行のそれぞれに、各クエリで指定される人物番号が 1 つずつ与えられる。すなわち、そのうち j 行目（1 \leq j \leq Q）には X_j が与えられる。

出力

Q 行にわたって出力せよ。j 行目（1 \leq j \leq Q）には、j 番目のクエリで指定された人物 X_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

Score : 366 pts

Problem Statement

Takahashi is investigating his family's genealogy. The family consists of N people, each numbered from 1 to N.

In this family tree, every person except person 1, who is the founding ancestor, has exactly one "parent." The parent of person i (2 \leq i \leq N) is person P_i. Through these parent-child relationships, all people form a rooted tree with person 1 as the root.

For each person i, the value V_i of the inheritance left by that person is recorded.

Takahashi defines the "cumulative inheritance" of a person X as the sum of the inheritance values of all people on the path from person X to the founding ancestor (person 1), obtained by repeatedly following the parent, including both person X themselves and person 1.

You are given Q queries. For each query, a person number X_j is specified. Find the cumulative inheritance of that person.

Constraints

  • 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)
  • All input values are integers

Input

The input is given from standard input in the following format.

N Q
V_1 V_2 \ldots V_N
P_2 P_3 \ldots P_N
X_1
X_2
\vdots
X_Q
  • The first line contains the number of people N and the number of queries Q, separated by a space.
  • The second line contains the inheritance values V_1, V_2, \ldots, V_N of each person, separated by spaces.
  • The third line contains the parent numbers P_2, P_3, \ldots, P_N for persons 2 through N, separated by spaces. When N = 1, this line is empty.
  • Each of the following Q lines contains a single person number specified for each query. Specifically, the j-th of these lines (1 \leq j \leq Q) contains X_j.

Output

Output Q lines. On the j-th line (1 \leq j \leq Q), output the cumulative inheritance of person X_j specified in the j-th query as an integer.

ans_1
ans_2
\vdots
ans_Q

Sample Input 1

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

Sample Output 1

10
70
80

Sample Input 2

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

Sample Output 2

100
400
550
450
800

Sample Input 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

Sample Output 3

1000000000
1700000000
1900000000
2100000000
1850000000
2250000000
1300000000
2100000000