题解:P11976 [KTSC 2021] 通信网络 / communication

· · 题解

先考虑断开割边的情况,答案是 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 就没有非树边,ufa_{fa_u} 就不连通,fa_u 成为割点。因此统计贡献就再求一遍 P(u,v) 上有多少 cov_e=1cut_{fa_u}=0,这里树上前缀和即可。

【删除树边】

重点在于删除树边 (u,fa_u) 的情形。边双连通分量的好处是删除树边后仍然连通,并且我们只关心所有跨过 (u,fa_u) 祖先链的点,否则别的点必然上下连通,而“上部分”就与删除树边那一块连通。因此新的割点 x 只能是 u 子树内的点或者 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_iu 子树,但是上端点为 u 祖先的 v_i\text{lca}=d(由于 G' 点双连通,所以 d 存在)。其中 d 的维护可以使用树上并查集从下往上维护,也可以描述成深度区间的限制。然后使用线段树,维护 dfs 序,并且支持区间加区间最小值个数即可维护。

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

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