题目描述

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

题目大意

给定一颗有 $n$ 个节点的树，带边权，要进行 $Q$ 次操作，操作有两种：

1 i w：将第 $i$ 条边的边权改为 $w$。
2 u v：询问 $u,v$ 两点的距离。

输入格式

第一行，一个正整数 $n$。
接下来 $n-1$ 行，每行三个数 $u,v,w$，表示一条树边。
接下来一个正整数 $Q$。
接下来 $Q$ 行，每行三个数，描述一个询问，格式如上。

输出格式

对于每个 $2$ 操作，输出一行一个数，表示该询问的答案。

说明/提示

$1\le n,Q\le 2\times10^5，1\le w_i\le 10^9$

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

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

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

提示

制約

• $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

木ははじめ、下の図のようになっています。  各クエリでは、以下のような処理を行います。 - $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}$ 整数に収まらない場合があることに注意してください。