AT_cpsco2019_s2_g MSTX

给定一个简单连通无向图，该图包含 $N$ 个顶点和 $M$ 条边。图中的第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，其权重为 $w_i$。权重 $w_i$ 可以是一个正整数常数，也可以是一个变量 $x$。请解答以下 $Q$ 个查询。 - 对于每个查询，第 $i$ 个查询将提供一个正整数 $a_i$。 - 你的任务是计算当 $x = a_i$ 时，图的最小生成树的总权重。

输入数据从标准输入中获取，具体格式如下： 字符 $c_i$ 为 `0` 或 `1`，用来标示 $w_i$ 是常数还是变量。如果 $c_i$ 为 `0`，则 $w_i$ 是一个正整数常数；如果 $c_i$ 为 `1`，则 $w_i$ 表示变量 $x$。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ c_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ c_2 $ $ w_2 $ $ \ldots $ $ u_M $ $ v_M $ $ c_M $ $ w_M $ $ Q $ $ a_1 $ $ a_2 $ $ \ldots $ $ a_Q $

输出包含 $Q$ 行，分别对应每个查询的答案。第 $i$ 行应输出对于查询 $a_i$ 的结果。

- 顶点数： $2 \le N \le 5 \times 10^4$ - 边数： $N - 1 \le M \le \min(5 \times 10^4, N(N-1)/2)$ - 对于每条边： $1 \le u_i, v_i \le N$ 且 $u_i \neq v_i$ - 边唯一性：任意两边 $i$ 和 $j$ 不可以满足 $(u_i, v_i) = (u_j, v_j)$ 或 $(u_i, v_i) = (v_j, u_j)$ - 图是连通的 - 常量边权重：当 $w_i$ 是常数时，满足 $1 \le w_i \le 10^9$ - 查询数： $1 \le Q \le 5 \times 10^4$ - 查询参数： $1 \le a_i \le 10^9$ - 输入中，除了 `x` 是字符，其他所有都是整数。 ### 样例解释 在给定的例子中： - 如果 $x \le 5$，那么最小生成树的权重为 $x + 1$。 - 如果 $x \ge 5$，那么最小生成树的权重为 $6$。 **本翻译由 AI 自动生成**