MST Query

题目描述

给你一个带权无向连通图 $G$，有 $N$ 个顶点和 $N-1$ 条边，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，权重为 $c_i$。 你需要按顺序处理 $Q$ 个查询。第 $i$ 个查询描述如下：

给定整数 $u_i, v_i, w_i$。在 $G$ 中在顶点 $u_i$ 和 $v_i$ 之间添加一条权重为 $w_i$ 的边。然后，输出图 $G$ 的最小生成树中所有边权重之和。

输入格式

输入从标准输入给出，格式如下： $N$ $Q$ $a_1$ $b_1$ $c_1$ $\vdots$ $a_{N-1}$ $b_{N-1}$ $c_{N-1}$ $u_1$ $v_1$ $w_1$ $\vdots$ $u_Q$ $v_Q$ $w_Q$

输出格式

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案。

4 4
1 2 6
2 3 5
2 4 4
1 3 3
1 2 3
1 4 10
3 4 1

12
10
10
7

8 6
1 8 8
1 6 10
1 5 8
2 6 6
6 7 6
1 3 9
2 4 7
1 3 4
1 6 7
3 4 6
1 5 1
7 8 4
3 5 3

49
46
45
38
34
33

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq Q \leq 2 \times 10^5$ 1 \leq a_i < b_i \leq N 1 \leq u_i < v_i \leq N $1 \leq c_i, w_i \leq 10$ 该图在处理查询之前是连通的。 所有输入值均为整数。Here is the graph after adding the edge for each query. The edges included in the minimum spanning tree are colored red.

标签: AtCoder|abc355F

来源

AtCoder|abc355F