P13342 [EGOI 2025] Wind Turbines / 风力涡轮机

Anna 负责为北海新建的一个海上风电场设计电缆布线。该风电场有 $N$ 台风力发电机，编号为 $0, 1, \ldots, N-1$。她的目标是确保所有发电机都能以最低的成本与陆地（岸边）连通。 Anna 拥有 $M$ 条可选的连接，每条连接都连接两台风力发电机，并有一个特定的费用。此外，附近的城市同意承担将一段连续编号区间 $[\ell, r]$ 内的发电机直接接入岸边的费用。也就是说，区间内的每台发电机 $t$（$\ell \leq t \leq r$）都可以免费直接接入岸边。如果所有可选连接都建成，则任意两台发电机之间都可以互相到达。这意味着只要有一台发电机接入岸边，就可以通过某些连接让所有发电机的电力都输送到岸边。当然，如果有更多发电机直接接入岸边，可能可以进一步降低总成本。注意，免费连接是唯一能直接连到岸边的方式。 Anna 的任务是选择一部分可选连接，使得它们的总费用最小，并保证每台发电机都能通过某些路径与岸边连通（可以经过其他发电机）。 为了让 Anna 做出明智的决策，城市方提供了 $Q$ 种不同的区间 $[\ell, r]$ 方案。城市方希望 Anna 计算在每种方案下的最小总费用。

第一行包含三个整数 $N$、$M$ 和 $Q$。 接下来的 $M$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $c_i$，表示一条可选的无向连接，连接发电机 $u_i$ 和 $v_i$，费用为 $c_i$。每对发电机之间至多有一条直接连接，且 $u_i \neq v_i$。保证如果所有可选连接都建成，任意两台发电机之间都可以互相到达。 接下来 $Q$ 行，每行两个整数 $\ell_i$ 和 $r_i$，表示一种方案，在该方案下，岸边直接接入区间 $[\ell_i, r_i]$ 内的所有发电机。注意，可能有 $r_i = \ell_i$，即岸边只直接接入一台发电机。

输出 $Q$ 行，每行一个整数，表示在对应方案下，使所有发电机都能把电送到岸边所需的最小总费用。

### 样例说明 在第一个样例中，给定如下图的可选连接：  有三种方案。第一种方案中，只有发电机 $1$ 直接接入岸边，此时需要保留除 $(0,2)$ 以外的所有连接，总费用为 $2 + 3 + 6 + 3 = 14$。第二种方案中，发电机 $3$ 和 $4$ 直接接入岸边，此时只需保留 $(1,0)$、$(1,2)$ 和 $(2,4)$，总费用为 $8$。第三种方案中，除了发电机 $0$ 以外，其他都直接接入岸边，此时只需将 $0$ 与任一发电机连接即可，选择 $(0,1)$，费用为 $2$。下图展示了三种方案的最优方案：  第一个和第六个样例满足测试组 $2$、$5$、$7$ 的约束。第二个和第七个样例满足测试组 $1$、$2$、$5$、$7$ 的约束。第三个样例满足测试组 $2$、$3$、$5$、$7$ 的约束。第四个样例满足测试组 $2$、$4$、$5$、$7$ 的约束。第五个样例满足测试组 $2$、$5$、$6$、$7$ 的约束。 ### 约束与评分 - $2 \leq N \leq 100000$ - $1 \leq M \leq 100000$ - $1 \leq Q \leq 200000$ - $0 \leq u_i, v_i \leq N-1$ - $u_i \neq v_i$，且每对发电机之间至多有一条直接连接 - $1 \leq c_i \leq 1000000000$ - $0 \leq \ell_i \leq r_i \leq N-1$ 你的解答将在一组测试组上进行评测，每组有若干测试用例。要获得该测试组的分数，你需要通过该测试组的所有测试用例。 | 组别 | 分值 | 限制条件 | | :-: | :-: | :-: | | 1 | 8 | $M = N - 1$，且第 $i$ 条连接为 $u_i = i$，$v_i = i + 1$，即所有连接连成一条链 $0 \leftrightarrow 1 \leftrightarrow 2 \leftrightarrow \ldots \leftrightarrow N - 1$ | | 2 | 11 | $N, M, Q \leq 2000$ 且 $\sum (r_i - \ell_i + 1) \leq 2000$ | | 3 | 13 | 对所有 $i$，$r_i = \ell_i + 1$ | | 4 | 17 | 对所有 $i$，$1 \leq c_i \leq 2$，即每条连接的费用为 $1$ 或 $2$ | | 5 | 16 | $\sum (r_i - \ell_i + 1) \leq 400000$ | | 6 | 14 | 对所有 $i$，$\ell_i = 0$ | | 7 | 21 | 无额外限制 |