自动搬运

查看原文

来自洛谷，原作者为

	nullqtr_pwp 我注意到有些人一直在做各种地方的cnoi题，但是并没有什么b用，可能是因为一直在舒适区里面舒服的卷，虐杀自己擅长的东西并获得成就感。

搬运于2025-08-24 23:11:49，当前版本为作者最后更新于2025-07-26 12:59:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先考虑断开割边的情况，答案是 $n$。注意特判断开后一侧大小恰好为 $1$ 的情况，此时答案为 $n-1$。接下来我们认为，断开的边都不是割边。考虑对于每个点双分开做，可以建立圆方树后求出所有点双，并预处理原图的割点个数，作为这个点双之外的贡献。那么在原图的割点在这个点双里面就不会有额外的贡献。令 $cut_u\in\{0,1\}$ 表示 $u$ 是否为原图 $G$ 的割点。

套路化地求出当前点双连通分量 $G'$ 的 $\text{DFS}$ 生成树 $T$，由经典结论只有树边和返祖边。

【删除返祖边】

对于删除返祖边 $(u,v)$ 的答案，找到所有在 $u\to v$ 路径上，并且不是这条路径最上面一条的树边集合 $P(u,v)$。对于每条树边 $e$，记录其在多少个返祖边的 $P(u,v)$ 中，记为 $num_e$。对于 $cov$，可以树上差分求。如果 $num_e=1$，令这条边是 $(u,fa_u)$，那么删除覆盖 $e$ 的那条边后，$e$ 就没有非树边，$u$ 和 $fa_{fa_u}$ 就不连通，$fa_u$ 成为割点。因此统计贡献就再求一遍 $P(u,v)$ 上有多少 $cov_e=1$ 且 $cut_{fa_u}=0$，这里树上前缀和即可。

【删除树边】

重点在于删除树边 $(u,fa_u)$ 的情形。边双连通分量的好处是删除树边后仍然连通，并且我们只关心所有跨过 $(u,fa_u)$ 祖先链的点，否则别的点必然上下连通，而“上部分”就与删除树边那一块连通。因此新的割点 $x$ 只能是 $u$ 子树内的点或者 $u$ 的祖先。

• $x$ 为 $u$ 子树的点。

此时 $x\ne u$，否则点 $u$ 自身就会把 $G'$ 分裂成进一步的点双。此时 $G'$ 分为根减去 $u$ 子树，$u$ 子树减去 $x$ 子树，以及 $x$ 的一堆子树。将其称为上，中，下。如果上和中有返祖边连接，此时 $(u,fa_u)$ 是否删去无所谓，$x$ 不可能成为割点；接下来上，中是不连通的。此时 $x$ 成为割点当且仅当不存在 $x$ 某个儿子 $s_i$ 的子树同时与上，中部分连通。

此时考虑下端点在 $s_i$ 子树，上端点在 $x$ 祖先的返祖边的上端点的深度，其对应区间 $[l,r]$，就要求 $dep_u\leq l$ 或者 $dep_u>r$。对于一个 $x$，考虑其所有 $s_i$，就可以得到 $\mathcal O(\deg_x)$ 个限制区间使得 $u$ 的深度不能在限制区间中。关于上，中部分没有边的限制，求出所有下端点 $v_i$ 在 $u$ 子树，但是上端点为 $u$ 祖先的 $v_i$ 的 $\text{lca}=d$（由于 $G'$ 点双连通，所以 $d$ 存在）。其中 $d$ 的维护可以使用树上并查集从下往上维护，也可以描述成深度区间的限制。然后使用线段树，维护 dfs 序，并且支持区间加区间最小值个数即可维护。

• $x$ 为 $u$ 的祖先。

特判掉 $x$ 为树根的 corner case。此时 $G'$ 分为根减去 $x$ 子树，$x$ 子树减去 $u$ 子树以及 $u$ 子树，还是分为上中下三部分。我们要求下面不同时与中和上连通。分为下端点在 $u$ 子树的返祖边的上端点均在 $x$ 或比 $x$ 更深的位置；以及均在 $x$ 或者比 $x$ 更浅的位置。

时间复杂度 $\mathcal O(n\log n)$。