G - Get the Salary of Atcoder Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MB

Max Score: 1450 Points

Problem Statement

There are N workers in Atcoder company. Each worker is numbered 0 through N - 1, and the boss for worker i is p_i like a tree structure and the salary is currently a_i. (p_i < i, especially p_0 = -1 because worker 0 is a president)
In atcoder, the boss of boss of boss of ... (repeated k times) worker i called "k-th upper boss", and "k-th lower subordinate" called for vice versa.

You have to process Q queries for Atcoder:
  • Query 1: You are given v_i, d_i, x_i. Increase the salary of worker v_i, and all j-th (1 ≤ j ≤ d_i) lower subordinates by x_i.
  • Query 2: You are given v_i, d_i. Calculate the sum of salary of worker v_i and all j-th (1 ≤ j ≤ d_i) lower subordinates.
  • Query 3: You are given pr_i, ar_i. Now Atcoder has a new worker c! (c is the current number of workers) The boss is pr_i, and the first salary is ar_i.
Process all queries!!!

Input Format

Let the i-th query query_i, the input format is following:
N Q
p_0 a_0
p_1 a_1
 :   :
p_{N - 1} a_{N - 1}
query_0
query_1
 :   :
query_{Q - 1}
THe format of query_i is one of the three format:
1 v_i d_i x_i

2 v_i d_i

3 pr_i ar_i

Output Format

Print the result in one line for each query 2.

Constraints

  • N ≤ 400000
  • Q ≤ 50000
  • p_i < i for all valid i.
  • In each question 1 or 2, worker v_i exists.
  • d_i ≤ 400000
  • 0 ≤ a_i, x_i ≤ 1000

Scoring

Subtask 1 [170 points]
  • N, Q ≤ 5000
Subtask 2 [310 points]
  • p_i + 1 = i for all valid i.
Subtask 3 [380 points]
  • There are no query 3.
Subtask 4 [590 points]
  • There are no additional constraints.

Sample Input 1

6 7
-1 6
0 5
0 4
2 3
2 2
1 1
2 0 1
1 0 2 1
2 2 1
3 3 3
2 0 3
3 3 4
2 1 1

Sample Output 1

15
12
30
8

Sample Input 2

7 9
-1 1
0 5
0 7
0 8
1 3
4 1
5 1
2 1 1
2 1 2
1 1 2 3
1 4 1 1
2 3 1
2 0 2
3 6 1
3 7 11
2 0 15

Sample Output 2

8
9
8
31
49
配点：1450 点

問題文

現在 N 人のAtcoder社員がいる。それぞれの人は 0 ～ N-1 で番号付けされている。
社員 i の直接の上司は p_i (p_i < i) である。ただし、社員 0 は社長であるため、p_0 = -1 である。また、社員 i の最初の給料は a_i である。
また、Atcoderでは、社員 i の上司の上司の上司の...上司 (k 回繰り返されるとする) を 「k 個上の上司」とし、その逆は「k 個下の部下」と呼ばれている。
また、次のような処理 / 質問を合計 Q 個処理しなければなりません。
  • タイプ1：v_i, d_i, x_i が与えられ、社員 v_i と、この j (1 ≤ j ≤ d_i) 個下の部下全員に対し、給料を x_i 上げる。(x_i は負のときもある)
  • タイプ2：v_i, d_i が与えられ、社員 v_i と、この j (1 ≤ j ≤ d_i) 個下の部下全員の給料の合計を求める。
  • タイプ3：pr_i, ar_i が与えられ、現在の社員数を c としたときに新入社員 c を pr_i の直接の部下として配置する。また最初の給料を ar_i とする。
そのとき、すべての質問に答えなさい。

入力

i 番目の処理 / 質問を query_i としたとき、次のような形式で与えられる。
N Q
p_0 a_0
p_1 a_1
 :   :
p_{N - 1} a_{N - 1}
query_0
query_1
 :   :
query_{Q - 1}
また、query_i は、次の3つの形式のどれかで与えられる。
1 v_i d_i x_i

2 v_i d_i

3 pr_i ar_i

出力

各質問2に対し、答えをそれぞれ1行に出力しなさい。

制約

  • N ≤ 400000
  • Q ≤ 50000
  • p_i < i が常に成立する
  • それぞれの処理 / 質問に対し、社員 v_i はその時点で存在する
  • d_i ≤ 400000
  • 0 ≤ a_i, x_i ≤ 1000

得点

小課題1 [170 点]
  • N, Q ≤ 5000
小課題2 [310 点]
  • p_i + 1 = i がすべての i に対して成立する。
小課題4 [380 点]
  • タイプ3のクエリは存在しない。
小課題5 [590 点]
  • 追加の制約はない。

入力例1

6 7
-1 6
0 5
0 4
2 3
2 2
1 1
2 0 1
1 0 2 1
2 2 1
3 3 3
2 0 3
3 3 4
2 1 1

出力例1

15
12
30
8

入力例2

7 9
-1 1
0 5
0 7
0 8
1 3
4 1
5 1
2 1 1
2 1 2
1 1 2 3
1 4 1 1
2 3 1
2 0 2
3 6 1
3 7 11
2 0 15

出力例2

8
9
8
31
49