K - 移住計画 (Migration Plan) Editorial /

Time Limit: 7.5 sec / Memory Limit: 2048 MiB

Score: 100 points

Problem Statement

JOI Kingdom consists of N cities numbered from 1 to N. There are N - 1 one-way roads connecting these cities. Specifically, for each i = 2, 3, \ldots, N, there is a road leading from city i to city P_{i}. Here, it is guaranteed that 1 \le P_{i} < i.

Each of the N cities has a defined danger level. The capital city, city 1, has a danger level of 0. For city i (2 \le i \le N), the danger level is defined as the number of roads traversed in the path from city i to city 1. Due to the structure of JOI Kingdom, there is exactly one unique path from any city i to city 1.

Currently, there are K_{i} beavers living in city i (1 \le i \le N). The president of JOI Kingdom, Bitaro, has planned a beaver relocation program. This relocation plan will be executed over Q days. On the j-th day (1 \le j \le Q), one of the following three types of events will occur:

  • Relocation: All beavers living in a city with danger level X_j at that moment will move to a city with danger level Y_j, which they can reach by traveling along one or more roads from their current city. It is guaranteed that 0 \le Y_j < X_j. Due to the structure of JOI Kingdom, the relocation destination for each beaver is uniquely determined.
  • Immigration: The number of beavers living in city A_j increases by L_j due to immigration from outside JOI Kingdom.
  • Survey: The number of beavers currently living in city B_j is surveyed.

As Bitaro’s subordinate, you realize that you can compute the number of beavers in each survey event based solely on the relocation plan’s information, without physically visiting the city.

Given the structure of JOI Kingdom, the current number of beavers living in each city, and the details of the relocation plan, write a program to compute the results of each survey event.

Input

Read the following data from the standard input.

N
P_2 P_3 \cdots P_N
K_1 K_2 \cdots K_N
Q
(\text{Query }1)
(\text{Query }2)
\vdots
(\text{Query }Q)

Each (Query j) (1 \le j \le Q) consists of several integers separated by spaces. Let the first integer be T_j. The contents of this line are as follows:

  • If T_{j} = 1, the line continues with two integers X_{j}, Y_{j} in this order. This indicates that on day j, a relocation event occurs, where all beavers living in a city with danger level X_{j} move to a city with danger level Y_{j} that they can reach by traveling along one or more roads from their current city.
  • If T_{j} = 2, the line continues with two integers A_{j}, L_{j} in this order. This indicates that on day j, an immigration event occurs, increasing the number of beavers in city A_{j} by L_{j}.
  • If T_{j} = 3, the line continues with one integer B_{j}. This indicates that on day j, a survey event occurs, where the number of beavers currently living in city B_{j} is surveyed.

Output

For each j (1 \le j \le Q) where T_{j} = 3, output the number of beavers in city B_{j} at that moment, one per line, in order.

Constraints

  • 2 \le N \le 2\,000\,000.
  • 1 \le P_{i} < i (2 \le i \le N).
  • 0 \le K_{i} \le 100 (1 \le i \le N).
  • 1 \le Q \le 2\,000\,000.
  • T_{j} is either 1, 2, or 3 (1 \le j \le Q).
  • If T_{j} = 1, then 0 \le Y_{j} < X_{j} \le N - 1 (1 \le j \le Q).
  • If T_{j} = 2, then 1 \le A_{j} \le N, 1 \le L_{j} \le 100 (1 \le j \le Q).
  • If T_{j} = 3, then 1 \le B_{j} \le N (1 \le j \le Q).
  • At least one j (1 \le j \le Q) satisfies T_{j} = 3.
  • All input values are integers.

Subtasks

Let the maximum danger level of the cities be D.

  1. (4 points) D = 1.
  2. (8 points) N \le 20.
  3. (13 points) D \le 20.
  4. (15 points) No queries satisfy T_{j} = 2, and at most 5 queries satisfy T_{j} = 3.
  5. (15 points) At most 5 queries satisfy T_{j} = 3.
  6. (27 points) No queries satisfy T_{j} = 2.
  7. (18 points) No additional constraints.

Sample Input 1

4
1 1 2
1 3 4 3
6
3 1
1 1 0
3 1
3 2
1 2 1
3 2

Sample Output 1

1
8
0
3

Initially, cities 1, 2, 3, 4 have 1, 3, 4, 3 beavers respectively. The danger levels of these cities are 0, 1, 1, 2, respectively.

  • On day 1, a survey event occurs. Output 1 on the first line, representing the number of beavers in city 1.
  • On day 2, a relocation event occurs. All beavers in city 2 and city 3 move to city 1. At the end of day 2, cities 1, 2, 3, 4 contain 8, 0, 0, 3 beavers, respectively.
  • On day 3, a survey event occurs. Output 8 on the second line.
  • On day 4, a survey event occurs. Output 0 on the third line.
  • On day 5, a relocation event occurs. All beavers in city 4 move to city 2. At the end of day 5, cities 1, 2, 3, 4 contain 8, 3, 0, 0 beavers, respectively.
  • On day 6, a survey event occurs. Output 3 on the fourth line.

This input example satisfies the constraints of subtasks 2, 3, 4, 5, 6, 7.

Sample Input 2

3
1 1
3 1 4
11
2 2 5
1 2 0
3 1
1 1 0
3 1
3 2
2 3 4
3 3
1 1 0
3 3
3 1

Sample Output 2

3
13
0
4
0
17

Initially, cities 1, 2, 3 have 3, 1, 4 beavers, respectively. The danger levels of these cities are 0, 1, 1, respectively.

  • On day 1, an immigration event occurs. The number of beavers in city 2 increases by 5. At the end of day 1, cities 1, 2, 3 contain 3, 6, 4 beavers, respectively.
  • On day 2, a relocation event occurs. No beavers move, as no city has a danger level of 2.
  • On day 3, a survey event occurs. Output 3 on the first line.
  • On day 4, a relocation event occurs. All beavers in city 2 and city 3 move to city 1. At the end of day 4, cities 1, 2, 3 contain 13, 0, 0 beavers, respectively.
  • On day 5, a survey event occurs. Output 13 on the second line.
  • On day 6, a survey event occurs. Output 0 on the third line.

Subsequent events occur similarly, but their descriptions are omitted.

This input example satisfies the constraints of subtasks 1, 2, 3, 7.

Sample Input 3

7
1 2 1 3 3 2
5 2 8 9 4 0 5
10
1 3 1
2 4 10
3 2
1 6 3
1 2 0
3 1
3 4
2 5 6
3 5
3 3

Sample Output 3

6
18
19
6
0

This input example satisfies the constraints of subtasks 2, 3, 5, 7.

配点 : 100 点

問題文

JOI 国には N 個の街があり,街には 1 から N までの番号が付けられている. これらの街の間を結ぶ N - 1 本の 一方通行 の道路がある. 具体的には,各 i = 2, 3, \ldots, N について,街 i から街 P_i に向かう道路がある. ここで,1 \leqq P_i < i が保証される.

N 個の街にはそれぞれ 危険度 が定義されている. 首都である街 1 の危険度は 0 である. 街 i (2\leqq i \leqq N) の危険度は,街 i から街 1 へ向かう経路において通る道路の本数として定義される. ここで,JOI 国の構造上,街 i から街 1 へ向かう経路はちょうど 1 つ存在することに注意せよ.

現在街 i (1\leqq i \leqq N) には K_i 匹のビーバーが住んでいる. JOI 国の大統領であるビ太郎はビーバーたちの移住計画を立てた. 移住計画はこれから Q 日間にわたって実行される. j 日目 (1\leqq j \leqq Q) には次の 3 種類のうちいずれか 1 つのイベントが発生する.

  • 移住
    その時点で危険度 X_j の街に住んでいるビーバー全員が,各々が住んでいる街から何本かの道路を通ってたどり着くことのできる危険度 Y_j の街へ移住する.ここで,0\leqq Y_j < X_j が保証される.JOI 国の構造上,各ビーバーについて,移住先が一意に定まることに注意せよ.

  • 移民受け入れ
    JOI 国外からの移民を受け入れることで,街 A_j に住むビーバーの数が L_j だけ増加する.

  • 調査
    その時点で街 B_j に住んでいるビーバーの数を調査する.

ビ太郎の部下であるあなたは,各調査イベントにおいて実際にその街を訪れなくとも移住計画の情報のみによってビーバーの数を計算できることに気づいた.

JOI 国の構造,現在住んでいるビーバーの数,および移住計画についての情報が与えられたとき,各調査イベントの結果を計算するプログラムを作成せよ.


入力

入力は以下の形式で標準入力から与えられる.

N
P_2 P_3 \cdots P_N
K_1 K_2 \cdots K_N
Q
(\text{Query }1)
(\text{Query }2)
\vdots
(\text{Query }Q)

各 (\text{Query }j) (1\leqq j \leqq Q) にはいくつかの整数が空白区切りで書かれている.そのうち 1 個目の整数を T_j とすると,この行の内容は次のいずれかである.

  • T_j = 1 のとき,この行には続いて,2 つの整数 X_j, Y_j がこの順に書かれている.これは j 日目のイベントが移住イベントで,その時点で危険度 X_j の街に住んでいるビーバー全員が,各々が住んでいる街から何本かの道路を通ってたどり着くことのできる危険度 Y_j の街へ移住することを表す.
  • T_j = 2 のとき,この行には続いて,2 つの整数 A_j, L_j がこの順に書かれている.これは j 日目のイベントが移民受け入れイベントで,街 A_j に住むビーバーの数が L_j だけ増加することを表す.
  • T_j = 3 のとき,この行には続いて,1 つの整数 B_j が書かれている.これは j 日目のイベントが調査イベントで,その時点で街 B_j に住んでいるビーバーの数を調査することを表す.

出力

j 日目のイベントが調査イベント,つまり T_j = 3 である j (1 \leqq j \leqq Q) それぞれに対して,調査イベントの結果を標準出力に順に 1 行ずつ出力せよ.

制約

  • 2 \leqq N \leqq 2\,000\,000.
  • 1 \leqq P_i < i (2 \leqq i \leqq N).
  • 0 \leqq K_i \leqq 100 (1 \leqq i \leqq N).
  • 1 \leqq Q \leqq 2\,000\,000.
  • T_j は 1, 2, 3 のいずれかである (1\leqq j \leqq Q).
  • T_j=1 のとき,0 \leqq Y_j < X_j \leqq N - 1 (1\leqq j \leqq Q).
  • T_j=2 のとき,1\leqq A_j \leqq N,1 \leqq L_j \leqq 100 (1\leqq j \leqq Q).
  • T_j=3 のとき, 1 \leqq B_j \leqq N (1\leqq j \leqq Q).
  • T_j=3 となる j (1\leqq j \leqq Q) が 1 つ以上存在する.
  • 入力される値はすべて整数である.

小課題

街の危険度の最大値を D とする.

  1. (4 点) D = 1.
  2. (8 点) N \leqq 20.
  3. (13 点) D\leqq 20.
  4. (15 点) T_j\neq 2 (1\leqq j\leqq Q).さらに,T_j = 3 となる j (1\leqq j\leqq Q) の個数は 5 以下.
  5. (15 点) T_j = 3 となる j (1\leqq j\leqq Q) の個数は 5 以下.
  6. (27 点) T_j\neq 2 (1\leqq j\leqq Q).
  7. (18 点) 追加の制約はない.

入力例 1

4
1 1 2
1 3 4 3
6
3 1
1 1 0
3 1
3 2
1 2 1
3 2

出力例 1

1
8
0
3

最初,街 1,2,3,4 にはそれぞれ 1,3,4,3 匹のビーバーが住んでいる. また,各街の危険度はそれぞれ 0,1,1,2 である.

1 日目は調査イベントが発生する. したがって,1 行目にはその時点で街 1 に住むビーバーの数である 1 を出力する.

2 日目は移住イベントが発生する. その時点で街 2 に住んでいるビーバーは街 1 に移動する. また,その時点で街 3 に住んでいるビーバーも街 1 に移動する. 2 日目の終了時点で,街 1,2,3,4 にはそれぞれ 8,0,0,3 匹のビーバーが住んでいる.

3 日目は調査イベントが発生する. したがって,2 行目にはその時点で街 1 に住むビーバーの数である 8 を出力する.

4 日目は調査イベントが発生する. したがって,3 行目にはその時点で街 2 に住むビーバーの数である 0 を出力する.

5 日目は移住イベントが発生する. その時点で街 4 に住んでいるビーバーは街 2 に移動する. 5 日目の終了時点で,街 1,2,3,4 にはそれぞれ 8,3,0,0 匹のビーバーが住んでいる.

6 日目は調査イベントが発生する. したがって,4 行目にはその時点で街 2 に住むビーバーの数である 3 を出力する.

この入力例は小課題 2,3,4,5,6,7 の制約を満たす.


入力例 2

3
1 1
3 1 4
11
2 2 5
1 2 0
3 1
1 1 0
3 1
3 2
2 3 4
3 3
1 1 0
3 3
3 1

出力例 2

3
13
0
4
0
17

最初,街 1,2,3 にはそれぞれ 3,1,4 匹のビーバーが住んでいる. また,各街の危険度はそれぞれ 0,1,1 である.

1 日目は移民受け入れイベントが発生する. 街 2 に住むビーバーの数が 5 だけ増える. 1 日目の終了時点で,街 1,2,3 にはそれぞれ 3,6,4 匹のビーバーが住んでいる.

2 日目は移住イベントが発生する. その時点で危険度が 2 の街に住んでいるビーバーはいないため,移動は起こらない.

3 日目は調査イベントが発生する. したがって,1 行目にはその時点で街 1 に住むビーバーの数である 3 を出力する.

4 日目は移住イベントが発生する. その時点で街 2 に住んでいるビーバーは街 1 に移動する. また,その時点で街 3 に住んでいるビーバーも街 1 に移動する. 4 日目の終了時点で,街 1,2,3 にはそれぞれ 13,0,0 匹のビーバーが住んでいる.

5 日目は調査イベントが発生する. したがって,2 行目にはその時点で街 1 に住むビーバーの数である 13 を出力する.

6 日目は調査イベントが発生する. したがって,3 行目にはその時点で街 2 に住むビーバーの数である 0 を出力する.

7 日目以降も同様にイベントが発生するが,ここでは説明を省略する.

この入力例は小課題 1,2,3,7 の制約を満たす.


入力例 3

7
1 2 1 3 3 2
5 2 8 9 4 0 5
10
1 3 1
2 4 10
3 2
1 6 3
1 2 0
3 1
3 4
2 5 6
3 5
3 3

出力例 3

6
18
19
6
0

この入力例は小課題 2,3,5,7 の制約を満たす.


Source Name

JOI 2024/2025 春季トレーニング Contest Day4