树上距离查询

题目描述

给定一棵有 $N$ 个顶点的树 $T$。第 $i$ 条边 $(1 \le i \le N-1)$ 连接顶点 $u _ i$ 和 $v _ i$，权重为 $w _ i$。

依次处理 $Q$ 个查询。查询有以下两种类型。

1 i w：将第 $i$ 条边的权重改为 $w$。

2 u v：输出顶点 $u$ 与顶点 $v$ 之间的距离。

这里，树中两个顶点 $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$

输出格式

输出 $q$ 行，其中 $q$ 是第二种查询的个数。第 $j$ 行 $(1 \le j \le q)$ 输出第 $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

第一个查询要求输出顶点 $2$ 与顶点 $3$ 之间的距离。边 $1$、边 $2$ 依次相连构成它们之间的一条路径，总权重为 $9$，这是最小值，因此输出 $9$。

第二个查询要求输出顶点 $1$ 与顶点 $5$ 之间的距离。边 $3$、边 $4$ 依次相连构成一条路径，总权重为 $19$，这是最小值，因此输出 $19$。

第三个查询把边 $3$ 的权重改为 $1$。

第四个查询要求输出顶点 $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

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 \le N \le 2 \times 10^5$
• $1 \le u _ i,v _ i \le N\ (1 \le i \le N-1)$
• $1 \le w _ i \le 10^9\ (1 \le i \le N-1)$
• 给定的图是一棵树
• $1 \le Q \le 2 \times 10^5$
• 对于每个第一种查询，$1 \le i \le N-1$，且 $1 \le w \le 10^9$
• 对于每个第二种查询，$1 \le u,v \le N$
• 至少有一个第二种查询
• 输入中的所有值均为整数

提示

注意，答案可能超出 32 位整数的范围。