自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 22:58:47，当前版本为作者最后更新于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)$。