AT_joi2026final_k JOI 国のお祭り事情 3 (Festivals in JOI Kingdom 3)

JOI 国は $ N $ 個の街と $ N-1 $ 本の国道からなり， 街には $ 1 $ から $ N $ までの番号が，国道には $ 1 $ から $ N-1 $ までの番号が付けられている． どの街からどの街へも，何本かの国道を通ることで移動できる． それぞれの街は，非負整数で表される**人気度**をもつ． 街 $ i $ ( $ 1 \leqq i \leqq N $ ) の人気度ははじめ $ C_i $ である． それぞれの国道は，正の整数で表される**所要時間**をもつ． 国道 $ j $ ( $ 1 \leqq j \leqq N-1 $ ) は街 $ A_j $ と街 $ B_j $ を双方向につないでおり，その所要時間ははじめ $ D_j $ である． JOI 国の街には聖火台が $ 1 $ つずつ設置されている． JOI 国のお祭りでは，街の聖火台に火をつけ，それを合図に街からパレードを出発させる伝統がある． 街 $ v $ と街 $ u $ が国道で直接つながれているとき，街 $ u $ は街 $ v $ に**隣接する**という． ある街の聖火台に火がつけられた時点で，隣接する街のそれぞれに向けて $ 1 $ つずつパレードが出発し， それが通る国道の所要時間と同じ時間をかけて歩いたあと，向かいの街に到着する． つまり，互いに隣接する街 $ v, u $ について，街 $ v $ の聖火台に火がつけられた時刻を $ t $ ，街 $ v, u $ を直接つなぐ国道の所要時間を $ d $ とすると， 街 $ v $ から出発するパレードが街 $ u $ に到着する時刻は $ t+d $ である． 街によっては，お祭りが始まった瞬間に火をつけるところもあれば，お祭りが盛り上がってきたタイミングで火をつけるところもある． お祭りが始まるタイミングを時刻 $ 0 $ とする． 街 $ i $ の聖火台に火をつける時刻は，街 $ i $ の人気度を $ c $ とすると，以下のように決定される． - $ c = 0 $ の場合，時刻 $ 0 $ に火をつける． - $ c \geqq 1 $ の場合，隣接する街から来て到着したパレードが $ c $ 個以上にはじめてなった時刻に火をつける． そのようなことが起こらない場合，火はつけない． これから K 理事長が JOI 国に滞在する． そのあいだに， JOI 国のお祭りについて $ Q $ 回の出来事がある． これらの出来事には，起きるのが早い順に $ 1 $ から $ Q $ までの番号が付けられている． 出来事 $ k $ ( $ 1 \leqq k \leqq Q $ )は以下の $ 3 $ 種類のいずれかである． - タイプ $ 1 $ : 街 $ V_k $ の人気度が $ X_k $ に変更される． - タイプ $ 2 $ : 国道 $ E_k $ の所要時間が $ X_k $ に変更される． - タイプ $ 3 $ : K 理事長が街 $ V_k $ に来る．このとき，仮にこの時点でお祭りが始まるとして，街 $ V_k $ の聖火台に火がつけられるかどうかを判定し，つけられる場合はその時刻を求めなければならない． JOI 国の構造，街の人気度，国道の所要時間，および滞在中の出来事の情報が与えられたとき， タイプ $ 3 $ の出来事において K 理事長がいる街の聖火台に火がつけられる時刻を計算するプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ B_1 $ $ D_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ D_{N-1} $ $ C_1 $ $ \vdots $ $ C_N $ $ Q $ (Query $ 1 $ ) $ \vdots $ (Query $ Q $ ) (Query $ k $ ) は出来事 $ k $ の情報を表す( $ 1 \leqq k \leqq Q $ )． (Query $ k $ ) にはいくつかの整数が空白区切りで書かれている． そのうち最初に書かれているものは出来事の種類を表す整数であり， $ 1,2,3 $ のいずれかである． これを $ P_k $ とすると，この行の内容は以下の $ 3 $ 種類のいずれかである． - $ P_k = 1 $ のとき，この行には続いて $ 2 $ 個の整数 $ V_k, X_k $ がこの順に書かれている． これは，街 $ V_k $ の人気度が $ X_k $ に変更されることを表す． - $ P_k = 2 $ のとき，この行には続いて $ 2 $ 個の整数 $ E_k, X_k $ がこの順に書かれている． これは，国道 $ E_k $ の所要時間が $ X_k $ に変更されることを表す． - $ P_k = 3 $ のとき，この行には続いて整数 $ V_k $ が書かれている． これは，K 理事長がこのとき街 $ V_k $ におり，仮にこの時点でお祭りが始まるとしたときに街 $ V_k $ の聖火台に火がつけられる時刻を求める必要があることを表す．

$ P_k = 3 $ である出来事 $ k $ ( $ 1 \leqq k \leqq Q $ ) それぞれに対して， K 理事長がいる街の聖火台に火がつけられる場合はその時刻を， 火がつけられない場合は `-1` を， $ k $ の昇順に改行区切りで出力せよ． ---

### 小課題 1. ( $ 6 $ 点) $ N \leqq 2\,000 $ ， $ Q \leqq 2\,000 $ ． 2. ( $ 7 $ 点) $ A_j = 1 $ ， $ B_j = j+1 $ ( $ 1 \leqq j \leqq N-1 $ )． $ P_k = 3 $ のとき $ V_k = 1 $ ( $ 1 \leqq k \leqq Q $ )． 3. ( $ 14 $ 点) $ N-1 $ は $ 3 $ の倍数． $ A_j = ((j - 1) \bmod \frac{N-1}{3}) + 1 $ ， $ B_j = j+1 $ ( $ 1 \leqq j \leqq N-1 $ )． $ P_k = 3 $ のとき $ V_k = 1 $ ( $ 1 \leqq k \leqq Q $ )． 4. ( $ 25 $ 点) $ P_k \neq 1 $ ． $ P_k = 3 $ のとき $ V_k = 1 $ ( $ 1 \leqq k \leqq Q $ )． 5. ( $ 12 $ 点) $ P_k = 3 $ のとき $ V_k = 1 $ ( $ 1 \leqq k \leqq Q $ )． 6. ( $ 22 $ 点) $ P_k \neq 1 $ ( $ 1 \leqq k \leqq Q $ )． 7. ( $ 14 $ 点) 追加の制約はない． --- ### Sample Explanation 1 出来事 $ 1 $ で想定されるお祭りにおいて，各街の聖火台に火がつく時刻は，時系列順に以下のとおりである． - 時刻 $ 0 $ に，街 $ 3,4,5,7 $ の聖火台に火がつく． - 時刻 $ 50 $ に，街 $ 2 $ の聖火台に火がつく．この時点で，街 $ 2 $ には 街 $ 3,5,7 $ からパレードが到着している． - 時刻 $ 80 $ に，街 $ 1 $ の聖火台に火がつく．この時点で，街 $ 1 $ には 街 $ 2,4 $ からパレードが到着している． - 時刻 $ 90 $ に，街 $ 6 $ の聖火台に火がつく．この時点で，街 $ 6 $ には 街 $ 1 $ からパレードが到着している． 街 $ 1 $ の聖火台に火がつく時刻は $ 80 $ なので， $ 80 $ を出力する． 出来事 $ 3 $ で想定されるお祭りにおいて，各街の聖火台に火がつく時刻は，時系列順に以下のとおりである． - 時刻 $ 0 $ に，街 $ 3,4,5,6,7 $ の聖火台に火がつく． - 時刻 $ 50 $ に，街 $ 2 $ の聖火台に火がつく．この時点で，街 $ 2 $ には 街 $ 3,5,7 $ からパレードが到着している． - 時刻 $ 70 $ に，街 $ 1 $ の聖火台に火がつく．この時点で，街 $ 1 $ には 街 $ 4,6 $ からパレードが到着している． 街 $ 1 $ の聖火台に火がつく時刻は $ 70 $ なので， $ 70 $ を出力する． 出来事 $ 5 $ で想定されるお祭りにおいて，各街の聖火台に火がつく時刻は，時系列順に以下のとおりである． - 時刻 $ 0 $ に，街 $ 3,4,5,6,7 $ の聖火台に火がつく． - 時刻 $ 30 $ に，街 $ 2 $ の聖火台に火がつく．この時点で，街 $ 2 $ には 街 $ 3,5,7 $ からパレードが到着している． - 時刻 $ 60 $ に，街 $ 1 $ の聖火台に火がつく．この時点で，街 $ 1 $ には 街 $ 2,6 $ からパレードが到着している． 街 $ 1 $ の聖火台に火がつく時刻は $ 60 $ なので， $ 60 $ を出力する． 出来事 $ 8 $ で想定されるお祭りにおいて，各街の聖火台に火がつく時刻は，時系列順に以下のとおりである． - 時刻 $ 0 $ に，街 $ 3,4,5,7 $ の聖火台に火がつく． 街 $ 1,2,6 $ の聖火台に火がつくことはない．街 $ 1 $ の聖火台に火がつくことはないので，`-1` を出力する． この入力例は小課題 $ 1,3,5,7 $ の制約を満たす． --- ### Sample Explanation 2 この入力例は小課題 $ 1,2,5,7 $ の制約を満たす． ### Constraints - $ 2 \leqq N \leqq 150\,000 $ ． - $ 0 \leqq C_i \leqq N $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq A_j < B_j \leqq N $ ( $ 1 \leqq j \leqq N-1 $ )． - $ 1 \leqq D_j \leqq 1\,000\,000 $ ( $ 1 \leqq j \leqq N-1 $ )． - どの街からどの街へも，何本かの国道を通ることで移動できる． - $ 1 \leqq Q \leqq 150\,000 $ ． - $ P_k = 1 $ のとき， $ 1 \leqq V_k \leqq N $ ， $ 0 \leqq X_k \leqq N $ ( $ 1 \leqq k \leqq Q $ )． - $ P_k = 2 $ のとき， $ 1 \leqq E_k \leqq N-1 $ ， $ 1 \leqq X_k \leqq 1\,000\,000 $ ( $ 1 \leqq k \leqq Q $ )． - $ P_k = 3 $ のとき， $ 1 \leqq V_k \leqq N $ ( $ 1 \leqq k \leqq Q $ )． - 入力される値はすべて整数である．