AT_tkppc2015_j 仕事をしよう！ (Working!)

[problemUrl]: https://atcoder.jp/contests/tkppc/tasks/tkppc2015_j 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となる。

出力はクエリ$ 3 $の数だけ行数がある。 $ i $行目には$ i $個目のクエリ3に対する答えを出力せよ。 出力の末尾にも改行を入れること。

### 配点 この問題には部分点がある。 - データセット1は、$ Q\ ≦\ 10^4 $を満たし、これに正解すると5点が得られる。 - データセット2では追加の制約はなく、これに正解すると155点が得られる。 ### Sample Explanation 1 この場合、次のようなことが行われている。 - クエリ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 $を出力する。 また、すべてのクエリを処理したとき都市は下の図のようになっている。 !\[\](/img/other/tsukukoma2015/asasffewe/g7.jpg) ### Sample Explanation 2 \### 出力例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 $を出力する。 また、すべてのクエリを処理したとき都市は下の図のようになっている。 !\[\](/img/other/tsukukoma2015/asasffewe/g8.jpg)