自动搬运

查看原文

来自洛谷，原作者为

	liangbowen 不能再摆了，，，

搬运于2025-08-24 22:49:15，当前版本为作者最后更新于2024-07-20 12:08:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

blog。提供一份代码短的题解。

一个暴力做法：维护 $w_i<w_{now}$ 与 $w_i\ge w_{now}$ 的前后缀 MST，查 $X_i$ 时将前后缀 MST 合并，直接求得答案。

考虑一棵 $(u_{now},v_{now},W)$ 的前缀 MST。因为 $w_i<W$ 时 $w_i$ 越大 $|W-w_i|$ 越小，所以枚举所有 $w_i<W$，按边权从大到小加边：

• 先忽略掉 $(u_{now},v_{now})$ 的边。
• 对于其他 $w_i<W$，尝试加入。如果成功加入并且构成了包含 $(u_{now},v_{now})$ 的环，显然需要删除最大边，加入最小边。显然最大边就是 $w_i$，最小边就是 $w_{now}$，删掉 $i$ 并加入 $now$。

找到这个 $i$。那么 $w_{now}$ 对答案有贡献，当且仅当询问的 $X$ 有 $X-w_i> w_{now}-X$，即 $X>\dfrac{w_i+w_{now}}2$。

同理，$w_i$ 在 $X>\dfrac{w_i+w_{now}}2$ 时会结束贡献。那么每条边都会有一个贡献区间，可以加入 MST 当且仅当在贡献区间内。

用并查集模拟上述算法，找出贡献区间 $[l_i,r_i]$，那么对于不同的 $X$，边 $i$ 的贡献为：

• $X<l_i$，没有贡献。
• $l_i\le X<w_i$，贡献为 $|X-w_i|=w_i-X$。
• $w_i\le X<r_i$，贡献为 $|X-w_i|=X-w_i$。
• $X\ge r_i$，没有贡献。

写个指针状物，因为询问的 $X_i$ 有序，顺着扫一遍即可。可以看代码理解。

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

写了 1.5k，其实应该可以写进 1k 的（