[ABC355] F - MST Query

F - MST Query

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 550 分

题面

给定一个有 个顶点和 条边的带权无向连通图 ，其中顶点编号为 到 ，边编号为 到 。第 条边连接顶点 和 ，边的权重为 。

给定 个查询依次进行处理。第 个查询描述如下：

• 给定整数 。在图 中顶点 和 之间添加一条权重为 的边。然后，打印 的最小生成树中所有边权重之和。

限制条件

• 在处理查询之前，图是连通的
• 所有输入值均为整数

---

输入

输入由标准输入给出，格式如下：

输出

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

---

输入样例 1

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

输出样例 1

12
10
10
7

添加每个查询的边后的图如下所示。最小生成树中包含的边用红色标出。

---

输入样例 2

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

输出样例 2

49
46
45
38
34
33