Luogu5360 [SDOI2019] 世界地图

题意： 一个左右相接的 网格图，边有边权。

每次挖掉一个区间的列之后，求剩余部分的 边权和。

，，时限 。

---

总思路：维护前缀、后缀生成树，询问时把前后缀通过链接 列的边连起来，再简化。

可以发现，在简化过程中，我们只关心第 列为关键点形成的虚树，且虚树中的每条边（对应一条链）视为其中权值最大的边。

从左到右逐步建立前缀生成树的虚树时，每次加入 条边跑 kruskal，复杂度 。询问将两侧虚树和 条边一起跑 kruskal，也是 。

复杂度 。