← 返回题目列表

AtCoder · abc294_g

G. 树上的距离查询

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

你得到一棵树 T 与 N 顶点。 边缘 i (1\leq i\leq N-1) 连接顶点 u _ i 和 v _ i,重量为 w _ i.

流程 Q 按顺序查询。查询有以下两种。

  • 1 i w : 改变边的权重 i to 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
\operatorname{query} _ 1
\operatorname{query} _ 2
\vdots
\operatorname{query} _ Q

在这里, \operatorname{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

示例输出 1

9
19
11

初始树如下图所示。

每个查询应按如下方式处理。

  • 第一个查询要求您打印顶点之间的距离 2 和顶点 3。边缘 1 和边缘 2,按此顺序,在它们之间形成一条总权重为 9,这是最小值,所以你应该打印 9.
  • 第二个查询要求您打印顶点之间的距离 1 和顶点 5。边缘 3 和边缘 4,按此顺序,在它们之间形成一条总权重为 19,这是最小值,所以你应该打印 19.
  • 第三个查询改变边的权重 3 to 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

示例输出 2

5000000000
4294967296

请注意,答案可能不适合 32- 位整数。


示例输入 3

1
1
2 1 1

示例输出 3

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

示例输出 4

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