P10517 国土规划

251Sec · 2024-05-26 20:47:54 · 题解

设 a_i=1 的点为关键点。

补集转化，求哪些点删去后存在关键点对互相不可达。对无向图建立圆方树，则这些点就是关键点虚树上的所有圆点。现在问题变为单点加入、单点删除、询问虚树包含圆点数量。

虚树上包含的圆点实际上相当于所有关键点到根节点（不妨设为 1）的路径的并，再去掉所有关键点 LCA 的父亲到根节点的路径。

先考虑前者如何计算，如果将所有关键点按照 DFS 序排序，设 P(u) 代表 u 到根的路径上的圆点数量，p_{1..k} 为关键点，则所求为 \sum\limits_{i=1}^k P(p_i)-P(\text{lca}(p_i,p_{i-1}))，其中 p_0=1。用 set 维护 DFS 序，每次加点删点引起的变化是 O(1)。

后者是容易的，只需要求出一个动态点集的 LCA，它的做法有很多。这里我们给出一种比较简单的做法：直接考虑 DFS 序最小和最大的点，点集里所有点的 LCA 就是这两个点的 LCA，结合上一段维护的 set，我们可以容易地实现这一部分。

总复杂度 O((n+q) \log n)。