配点 : $600$ 点

問題文

$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$ を両端点とするパスに含まれる辺の重みの合計として得られる値のうち最小のものです。

制約

• $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$
• $1\leq i\leq N-1$
• $1\leq w\leq 10^9$
• $2$ 番目の形式のクエリについて、- $1\leq u,v\leq N$
• $1\leq u,v\leq N$
• $2$ 番目の形式のクエリが $1$ つ以上存在する
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$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$ 個目のものに対する答えを出力せよ。

5
1 2 3
1 3 6
1 4 9
4 5 10
4
2 2 3
2 1 5
1 3 1
2 1 5

9
19
11

木ははじめ、下の図のようになっています。

各クエリでは、以下のような処理を行います。

• $1$ つめのクエリでは、頂点 $2$ と頂点 $3$ の距離を出力します。辺 $1$ と辺 $2$ をこの順に使うことで重みの合計が $9$ であるようなパスが得られ、これが最小なので $9$ を出力します。
• $2$ つめのクエリでは、頂点 $1$ と頂点 $5$ の距離を出力します。辺 $3$ と辺 $4$ をこの順に使うことで重みの合計が $19$ であるようなパスが得られ、これが最小なので $19$ を出力します。
• $3$ つめのクエリでは、辺 $3$ の重みを $1$ に変更します。
• $4$ つめのクエリでは、頂点 $1$ と頂点 $5$ の距離を出力します。辺 $3$ と辺 $4$ をこの順に使うことで重みの合計が $11$ であるようなパスが得られ、これが最小なので $11$ を出力します。

7
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
3
2 1 6
1 1 294967296
2 1 6

5000000000
4294967296

答えが $32\operatorname{bit}$ 整数に収まらない場合があることに注意してください。

1
1
2 1 1

0

8
1 2 105
1 3 103
2 4 105
2 5 100
5 6 101
3 7 106
3 8 100
18
2 2 8
2 3 6
1 4 108
2 3 4
2 3 5
2 5 5
2 3 1
2 4 3
1 1 107
2 3 1
2 7 6
2 3 8
2 1 5
2 7 6
2 4 7
2 1 7
2 5 3
2 8 6

308
409
313
316
0
103
313
103
525
100
215
525
421
209
318
519