题目描述

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

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

输入格式

第一行，一个正整数 $n$。

接下来 $n-1$ 行，每行三个数 $u,v,w$，表示一条树边。

接下来一个正整数 $Q$。

接下来 $Q$ 行，每行三个数，描述一个询问，格式如上。

输出格式

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

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\leq i\leq N-1$ 和
  • $1\leq w\leq 10^9$ .
• 对于每个第二类查询、
  • $1\leq u,v\leq N$ .
• 至少有一个第二类查询。
• 输入值均为整数。

样例 1 解释

初始树如下图所示。

每个查询的处理过程如下。

• 第一个查询要求打印顶点 $2$ 和顶点 $3$ 之间的距离。按照这个顺序，边 $1$ 和边 $2$ 之间形成的路径总重量为 $9$ ，这是最小值，所以应该打印 $9$ 。
• 第二个查询要求您打印顶点 $1$ 和顶点 $5$ 之间的距离。按照这个顺序，边 $3$ 和边 $4$ 之间形成的路径总重量为 $19$ ，这是最小值，因此应该打印 $19$ 。
• 第三个查询会将边 $3$ 的权重改为 $1$ 。
• 第四个查询要求打印顶点 $1$ 和顶点 $5$ 之间的距离。按照这个顺序，边 $3$ 和边 $4$ 之间形成的路径总重量为 $11$ ，这是最小值，因此您应该打印 $11$ 。