C - 水やり 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は植物園の管理人です。植物園には N 本の植物があり、植物には 1 から N までの番号が付けられています。これらの植物は木構造で管理されており、植物 1 を根とする根付き木を成しています。

各植物 i（2 \leq i \leq N）について、植物 P_i は植物 i の親です。

各植物は水分量と呼ばれる値を持っており、すべての植物の水分量は最初 0 です。

高橋君は Q 回の水やり作業を行います。j 回目（1 \leq j \leq Q）の水やりでは、植物 X_j を根とする部分木に含まれるすべての植物の水分量を D_j だけ増加させます。ここで、植物 X_j を根とする部分木とは、植物 X_j 自身と、植物 X_j のすべての子孫からなる集合です。

Q 回の水やり作業がすべて行われた後の、各植物の水分量を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq P_i \leq i - 1 （2 \leq i \leq N）
  • 1 \leq X_j \leq N （1 \leq j \leq Q）
  • 1 \leq D_j \leq 10^9 （1 \leq j \leq Q）
  • 入力はすべて整数である。

入力

N Q
P_2 P_3 \ldots P_N
X_1 D_1
X_2 D_2
\vdots
X_Q D_Q
  • 1 行目には、植物の本数を表す整数 N と、水やり作業の回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、植物 2 から植物 N までの親を表す N - 1 個の整数 P_2, P_3, \ldots, P_N が、スペース区切りで与えられる。P_i は植物 i の親の番号である。N = 1 のときは、この行には何も書かれていない（空行が与えられる）。
  • 3 行目から Q 行にわたって、水やり作業の内容が与えられる。2 + j 行目には、j 回目の水やり対象の植物の番号 X_j と水分増加量 D_j が、スペース区切りで与えられる。

出力

N 個の整数をスペース区切りで 1 行に出力せよ。i 番目の値は、すべての水やり作業実行後の植物 i の水分量である。

入力例 1

5 2
1 1 2 2
1 10
2 5

出力例 1

10 15 10 15 15

入力例 2

7 3
1 1 2 2 3 3
3 20
1 5
5 100

出力例 2

5 5 25 5 105 25 25

入力例 3

10 4
1 2 3 3 3 1 7 7 9
1 3
3 7
7 2
9 10

出力例 3

3 3 10 10 10 10 5 5 15 15

Score : 366 pts

Problem Statement

Takahashi is a caretaker of a botanical garden. The botanical garden has N plants, numbered from 1 to N. These plants are managed in a tree structure, forming a rooted tree with plant 1 as the root.

For each plant i (2 \leq i \leq N), plant P_i is the parent of plant i.

Each plant has a value called moisture level, and the moisture level of every plant is initially 0.

Takahashi performs Q watering operations. In the j-th operation (1 \leq j \leq Q), he increases the moisture level of all plants in the subtree rooted at plant X_j by D_j. Here, the subtree rooted at plant X_j is the set consisting of plant X_j itself and all descendants of plant X_j.

Determine the moisture level of each plant after all Q watering operations have been performed.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
  • 1 \leq X_j \leq N (1 \leq j \leq Q)
  • 1 \leq D_j \leq 10^9 (1 \leq j \leq Q)
  • All input values are integers.

Input

N Q
P_2 P_3 \ldots P_N
X_1 D_1
X_2 D_2
\vdots
X_Q D_Q
  • The first line contains an integer N representing the number of plants and an integer Q representing the number of watering operations, separated by a space.
  • The second line contains N - 1 integers P_2, P_3, \ldots, P_N separated by spaces, representing the parents of plants 2 through N. P_i is the number of the parent of plant i. When N = 1, nothing is written on this line (an empty line is given).
  • Over the next Q lines starting from the third line, the details of the watering operations are given. The (2 + j)-th line contains the plant number X_j targeted by the j-th watering operation and the moisture increase amount D_j, separated by a space.

Output

Output N integers separated by spaces on a single line. The i-th value should be the moisture level of plant i after all watering operations have been performed.

Sample Input 1

5 2
1 1 2 2
1 10
2 5

Sample Output 1

10 15 10 15 15

Sample Input 2

7 3
1 1 2 2 3 3
3 20
1 5
5 100

Sample Output 2

5 5 25 5 105 25 25

Sample Input 3

10 4
1 2 3 3 3 1 7 7 9
1 3
3 7
7 2
9 10

Sample Output 3

3 3 10 10 10 10 5 5 15 15