当前没有测试数据。

G - 树上距离查询

给定一个有 $N$ 个节点的树 $T$。 边 $i$ $(1\leq i\leq N-1)$ 连接节点 $u _ i$ 和 $v _ i$，并且其权重为 $w _ i$。

按照顺序处理 $Q$ 个查询。有两种查询如下所示。

• 1 $i$ $w$ : 将边 $i$ 的权重改为 $w$。
• 2 $u$ $v$ : 输出节点 $u$ 和节点 $v$ 之间的距离。

这里，树上节点 $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\leq i\leq N-1$
  • $1\leq w\leq 10^9$.
• 对于每一个第二种查询,
  • $1\leq u,v\leq N$.
• 第二种查询至少有一个。
• 输入中的所有值都是整数。

输入

输入从标准输入开始，包含以下内容：

$N$

$u _ 1$ $v _ 1$ $w _ 1$

$u _ 2$ $v _ 2$ $w _ 2$

$\vdots$

$u _ {N-1}$ $v _ {N-1}$ $w _ {N-1}$

$Q$

Query$_1$

Query$_2$

$\vdots$

Query$_Q$

这里，Query$_i$ 表示第 $i$ 个查询，并且满足以下格式中的一个。

1 $i$ $w$

2 $u$ $v$

输出

输出 $q$ 行，其中 $q$ 是第二种查询的数量。 第 $j$ 行 ($1\leq j\leq q$) 应包含第 $j$ 个第二种查询的答案。

样例 1

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

对应的初始树如图示所示。 每个查询的处理如下。

• 第一个查询要求输出节点 $2$ 和节点 $3$ 之间的距离。边 $1$ 和边 $2$ 依次构成一条连接它们的路径，路径上权重之和为 $9$，是最小值，因此输出 $9$。
• 第二个查询要求输出节点 $1$ 和节点 $5$ 之间的距离。边 $3$ 和边 $4$ 依次构成一条连接它们的路径，路径上权重之和为 $19$，是最小值，因此输出 $19$。
• 第三个查询将边 $3$ 的权重改为 $1$。
• 第四个查询要求输出节点 $1$ 和节点 $5$ 之间的距离。边 $3$ 和边 $4$ 依次构成一条连接它们的路径，路径上权重之和为 $11$，是最小值，因此输出 $11$。

样例 2

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$ 位整数。

样例 3

1
1
2 1 1

0

样例 4

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