P4764

Sampson_YW · 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。