/ 
Time Limit: 7 sec / Memory Limit: 512 MB
問題文
joisinoお姉ちゃんは気がつくと家のテレビの前に座っていた。
今まで夢でも見ていたのだろうか？
ただテレビを見始めてから相当の時間がたっていたようで、壁にかかっている時計は仕事が始まる1時間前をさしていた。
だが幸いなことにjoisinoお姉ちゃんが勤めている市役所は家からとても近い。
というわけで悠々と職場に着いたjoisinoお姉ちゃんは、いきなり自分が道路整備課に配属されたことを知らされた。
この市は今、都市開発がとても盛んでそれに伴う交通事情の悪化が懸念されている。
そこで市はjoisinoお姉ちゃんに交通事情の把握を任せることにした。
この市は今の時点では1つの都市が存在している。
だがこれから都市開発によって都市の数が増えることが予想される。
この市は新たに都市を作るときは、既存の都市を1つ選んで新しい都市との間に道を作る。
よってすべての時において、都市の数をnとするとn-1本の道が存在している。
また、はじめにあった都市は都市0と呼ばれ、i(1 ≦ i)番目に作られた都市は都市i、i(1 ≦ i)番目に作られた道は道iと呼ばれる。
また、この市ではそれぞれの都市の人口も変化しているので、それぞれの道の所要時間も変化していく。
それに加えて、住民の利便性の向上のためある都市から最も行くのに時間のかかる都市への所要時間を知る必要もある。
このような状況の中でjoisinoお姉ちゃんには都市に関するクエリがQ個与えられる。
i(1 ≦ i ≦ Q)番目の情報は次の3種類のどれかである。
- クエリ1･･･都市が新しく作られ、その都市はA_iと所要時間C_iの道で結ばれた。
- クエリ2･･･道A_iの所要時間がC_iに変わった。
- クエリ3･･･都市A_iから最も行くのに時間のかかる都市への所要時間を知る必要がある。
このうちクエリ3が来たときにはそれに答えないといけない。
しかし、この仕事はとても厄介なので、手作業でやっていると職場で暮らすことになってしまう。
そこでjoisinoお姉ちゃんはプログラムを組んでこの仕事を代わりにやってもらおうと思った。
入力
入力は以下の形式で標準入力から与えられる。
Q T_1 A_1 C_1 T_2 A_2 C_2 ： T_Q A_Q C_Q
- 1行目には、クエリの数Q(1 ≦ Q ≦ 5*10^5)が与えられる
- 2行目からのQ行のうちi行目にはi番目のクエリが書かれており、T_i(1 ≦ T_i ≦ 3),A_i(0 ≦ A_i ≦ 今ある都市の数-1),C_iが空白区切りで与えられる。
- T_iはクエリの種類を表している。
- T_i = 1のときは都市が新しく作られ、その都市は都市A_iと所要時間C_i(1 ≦ C_i ≦ 10^9)の道で結ばれたことを表している。
- T_i = 2のときは道A_iの所要時間がC_i(1 ≦ C_i ≦ 10^9)に変わったことを表している。
- T_i = 3のときは都市A_iから最も行くのに時間のかかる都市への所要時間を知る必要があることを表している。C_iは無視してよい。また、都市が1つしかない場合はこの答えは0となる。
配点
この問題には部分点がある。
- データセット1は、Q ≦ 10^4を満たし、これに正解すると5点が得られる。
- データセット2では追加の制約はなく、これに正解すると155点が得られる。
出力
出力はクエリ3の数だけ行数がある。
i行目にはi個目のクエリ3に対する答えを出力せよ。
出力の末尾にも改行を入れること。
入力例1
6 1 0 10 1 1 7 3 1 0 2 2 5 1 0 17 3 0 0
出力例1
10 17
この場合、次のようなことが行われている。
- クエリ1のタイプは1なので都市1が新たに作られ都市0と所要時間10の道で結ばれる。
- クエリ2のタイプは1なので都市2が新たに作られ都市1と所要時間7の道で結ばれる。
- クエリ3のタイプは3なので都市1から最も行くのに時間のかかる都市への所要時間を出力する。この場合は都市0へ行くときの10を出力する。
- クエリ4のタイプは2なので道2の所要時間が5に変更される。
- クエリ5のタイプは1なので都市3が新たに作られ都市0と所要時間17の道で結ばれる。
- クエリ6のタイプは3なので都市0から最も行くのに時間のかかる都市への所要時間を出力する。この場合は都市3へ行くときの17を出力する。
入力例2
7 3 0 0 1 0 10 2 1 15 1 0 7 1 2 5 1 2 8 3 0 0
出力例2
0 15
この場合、次のようなことが行われている。
- クエリ1のタイプは3なので都市0から最も行くのに時間のかかる都市への所要時間を出力する。この場合はほかに都市がないので0を出力する。
- クエリ2のタイプは1なので都市1が新たに作られ都市0と所要時間10の道で結ばれる。
- クエリ3のタイプは2なので道1の所要時間が15に変更される。
- クエリ4のタイプは1なので都市2が新たに作られ都市0と所要時間7の道で結ばれる。
- クエリ5のタイプは1なので都市3が新たに作られ都市2と所要時間5の道で結ばれる。
- クエリ6のタイプは1なので都市4が新たに作られ都市2と所要時間8の道で結ばれる。
- クエリ7のタイプは3なので都市0から最も行くのに時間のかかる都市への所要時間を出力する。この場合は都市1や都市4へ行くときの15を出力する。
入力例3
10 1 0 234 1 1 354 2 1 145 2 1 456 2 1 51 3 0 0 1 0 352 3 0 0 2 1 234 3 3 0
出力例3
405 405 940