自动搬运

查看原文

来自洛谷，原作者为

	Sampson_YW 你弱归你弱，YW比你弱。

搬运于2025-08-24 22:03:22，当前版本为作者最后更新于2023-07-27 18:54:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个小清新做法，不需要什么复杂的数据结构。

首先按边权从小到大排序。

然后对于每条边，我们要求出边权以它为最小值时构成的最小生成树的所有边。因为生成树最多只有 $n - 1$ 条边，所以可以花费 $O(nm)$ 的空间存下来。

考虑按边权从大到小做这件事情。

容易发现第 $i$ 条边的最小生成树可以直接从第 $i + 1$ 条边的最小生成树继承下来：要么去掉一条边再加入第 $i$ 条边，要么直接加入第 $i$ 条边。

于是只需要花费 $O(nm)$ 的时间即可求出 $m$ 棵生成树。

然后考虑询问，求边权在 $[L, R]$ 中的最小生成树边权值和。

那么你直接找到最小的那条边权 $\ge L$ 的边，它一定在最小生成树中。

然后你把它的最小生成树按边权从小到大排序，二分找到最大的 $\le R$ 的边，只需要求一个边权的前缀和即可。

但是直接做前缀和空间会爆掉。那么你考虑类似分段打表的方法，隔 $10$ 个数记录一次前缀和即可。

时间复杂度 $O((nm + q)\log n)$，空间复杂度 $O(nm)$，code。