[R25E]生成树 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个 $n$ 个顶点的无向完全图，一开始边权均为 $X$。现给出 $m$ 种操作，第 $i$ 种操作可以将 $u_i$ 和 $v_i$ 之间的权值修改为 $w_i$。（当然，你可以选择不执行该操作）

现在有 $Q$ 次独立的询问。每次询问会给出一个值 $x_j$，你需要确定权值 $X$ 被设为 $x_j$ 时，这 $n$ 个点完全图的最小生成树（MST）的总权值是多少。

对于一个带权无向连通图，其最小生成树是一个子图，满足以下条件：

1. 包含原图中所有的 $n$ 个顶点。
2. 自身构成一棵树。
3. 其包含的边的权值之和在所有可能的生成树中是最小的。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示顶点数量和操作的数量。

接下来的 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$，描述一个操作：连接顶点 $u_i$ 和 $v_i$ 的权值修改为 $w_i$。

之后的一行是一个整数 $Q$，表示询问的数量。

接下来的 $Q$ 行，每行一个整数 $x_j$，表示一次询问中一开始边的权值。

输出格式

输出 $Q$ 行，每行一个整数，依次对应每次询问计算出的最小生成树的权值。

样例

样例输入 #1

5 4
1 2 10
2 3 30
1 3 60
4 5 90
4
5
40
60
100

样例输出 #1

20
120
160
230

数据规模

对于 $40\%$ 的数据，$1 \leq n,m,Q \leq 1000$。

对于 $100\%$ 的数据，$1 \leq n ,m \leq 5 \times 10^5, 1\leq Q \leq 10^5, 1 \leq x_i ,w_i \leq 10^9$。