AT_joisp2025_k 移住計画 (Migration Plan)

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 $ 行ずつ出力せよ．

### 小課題 街の危険度の最大値を $ 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 $ 点) 追加の制約はない． --- ### Sample Explanation 1 最初，街 $ 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 $ の制約を満たす． --- ### Sample Explanation 2 最初，街 $ 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 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 2,3,5,7 $ の制約を満たす． ### Constraints - $ 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 $ つ以上存在する． - 入力される値はすべて整数である．