AT_abc294_g [ABC294G] Distance Queries on a Tree

[problemUrl]: https://atcoder.jp/contests/abc294/tasks/abc294_g $ N $ 頂点の木 $ T $ が与えられます。 辺 $ i $ $ (1\leq\ i\leq\ N-1) $ は頂点 $ u\ _\ i $ と $ v\ _\ i $ を結んでおり、重みは $ w\ _\ i $ です。 次の $ 2 $ 種類のクエリが合計 $ Q $ 個与えられるので、順に処理してください。 - `1 i w`：辺 $ i $ の重みを $ w $ に変更する。 - `2 u v`：頂点 $ u $ と頂点 $ v $ の距離を出力する。 ただし、木の $ 2 $ 頂点 $ u,v $ の距離とは、$ u $ と $ v $ を両端点とするパスに含まれる辺の重みの合計として得られる値のうち最小のものです。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ u\ _\ 1 $ $ v\ _\ 1 $ $ w\ _\ 1 $ $ u\ _\ 2 $ $ v\ _\ 2 $ $ w\ _\ 2 $ $ \vdots $ $ u\ _\ {N-1} $ $ v\ _\ {N-1} $ $ w\ _\ {N-1} $ $ Q $ $ \operatorname{query}\ _\ 1 $ $ \operatorname{query}\ _\ 2 $ $ \vdots $ $ \operatorname{query}\ _\ Q $ ただし、$ \operatorname{query}\ _\ i $ は $ i $ 個目のクエリを表しており、次の形式のいずれかで与えられる。 > $ 1 $ $ i $ $ w $ > $ 2 $ $ u $ $ v $

$ 2 $ 番目の形式のクエリの個数を $ q $ 個として $ q $ 行出力せよ。 $ j $ 行目 $ (1\leq\ j\leq\ q) $ には、$ 2 $ 番目の形式のクエリのうち $ j $ 個目のものに対する答えを出力せよ。

### 制約 - $ 1\leq\ N\leq\ 2\times10^5 $ - $ 1\leq\ u\ _\ i,v\ _\ i\leq\ N\ (1\leq\ i\leq\ N-1) $ - $ 1\leq\ w\ _\ i\leq\ 10^9\ (1\leq\ i\leq\ N-1) $ - 与えられるグラフは木 - $ 1\leq\ Q\leq\ 2\times10^5 $ - $ 1 $ 番目の形式のクエリについて、 - $ 1\leq\ i\leq\ N-1 $ - $ 1\leq\ w\leq\ 10^9 $ - $ 2 $ 番目の形式のクエリについて、 - $ 1\leq\ u,v\leq\ N $ - $ 2 $ 番目の形式のクエリが $ 1 $ つ以上存在する - 入力はすべて整数 ### Sample Explanation 1 木ははじめ、下の図のようになっています。 !\[\](https://img.atcoder.jp/abc294/1c9b492c4f32b51b95297739ec65fefe.png) 各クエリでは、以下のような処理を行います。 - $ 1 $ つめのクエリでは、頂点 $ 2 $ と頂点 $ 3 $ の距離を出力します。辺 $ 1 $ と辺 $ 2 $ をこの順に使うことで重みの合計が $ 9 $ であるようなパスが得られ、これが最小なので $ 9 $ を出力します。 - $ 2 $ つめのクエリでは、頂点 $ 1 $ と頂点 $ 5 $ の距離を出力します。辺 $ 3 $ と辺 $ 4 $ をこの順に使うことで重みの合計が $ 19 $ であるようなパスが得られ、これが最小なので $ 19 $ を出力します。 - $ 3 $ つめのクエリでは、辺 $ 3 $ の重みを $ 1 $ に変更します。 - $ 4 $ つめのクエリでは、頂点 $ 1 $ と頂点 $ 5 $ の距離を出力します。辺 $ 3 $ と辺 $ 4 $ をこの順に使うことで重みの合計が $ 11 $ であるようなパスが得られ、これが最小なので $ 11 $ を出力します。 ### Sample Explanation 2 答えが $ 32\operatorname{bit} $ 整数に収まらない場合があることに注意してください。