题解 P3206 【[HNOI2010]城市建设】

· · 题解

神仙题。。。

首先考虑线段树分治，按照时间建出线段树，然后我们考虑对于分治终点l=r暴力修改，但是这样每次的边集都是m，显然无法通过，不过这道题有两个小trick：

$2.$如果我们将区间$[l,r]$的边权都设为$INF$，跑一遍$MST$，这时不在$MST$中的边就可以直接删去了。 有了这两个小$trick$，不难证明对于区间$[l,r]$，点和边的规模都是$r-l$的。 还是证明一下吧： 考虑到第一个操作，最多会有$r-l$个点不能被缩，因此点的规模是$r-l$的，第二个操作保证了边的规模与点同阶。 总复杂度$nlog^2n$。