一些约定
下文中的 \(x\) 的祖先,都指位于 \(\bm{fa_x}\) 到根节点路径上的点(也就是不包括 \(x\))。
对于无向图 DFS 生成树中的一条返祖边,我们称深度较浅的那端为上端点,深度较深的那端为下端点。
题意
对于一张无向图,若将某个点删去后图不连通,则称这个点是危险的。给定一张 \(n\) 个点 \(m\) 条边的无向连通图,对于每条边,求出将这条边从图中删去后危险的点的数量。\(2\leq n\leq 2.5\times 10^5\),\(1\leq m\leq 10^6\)。
题解
感谢 @Miraik 和我讨论本题的相关做法。
KTSC 好难啊。
比较复杂的图结构分析题。
首先特判删的边是一条割边的情况,此时删去这条边后图已经不连通了,设分裂出的两个连通块分别是 \(S_1,S_2\),则答案为 \(n-[|S_1|=1]-[|S_2|=1]\)。
接下来假定删去的边不是割边,那么危险的点的就等价于割点了。我们发现,删去一条边后,割点的数量不会减少,且只可能让和这条边处于同一个点双的点从不是割点变成割点。于是考虑对每一个点双分开做,对于每一个点双 \(G'\),我们建出其 DFS 生成树,考虑分类讨论删去的边是树边还是返祖边。
返祖边
设这条返祖边为 \((u,v)\),其中 \(dep_u>dep_v\),考虑删去这条边会让哪些点变成割点。考察割点判定条件 \(low_v\geq dfn_u\),可以发现此时一定是删去这条树边后,某个点 \(v\) 的 \(low_v\) 变成了 \(dfn_v\),也就是回不到上面了,从而使得 \(fa_v\) 变为割点。
刻画这个条件,对于每条树边记录其被覆盖次数 \(cov_e\),对于每条返祖边 \((u,v)\),设 \(v\) 在 \(u\) 方向上的儿子为 \(s\),我们给其覆盖范围 \(C(u,v)=\operatorname{path}(u,v)\backslash (v,s)\) 中的边的 \(cov\) 加 \(1\)。然后每条返祖边 \((u,v)\) 的答案就是
其中 \(cut_u\) 表示点 \(u\) 是否为割点。注意这里之所以把 \((v,s)\) 去掉是因为删去 \((u,v)\) 并不会让 \(cut_v\) 发生改变。
容易想到使用树上差分维护上述过程。具体来说,对于每条返祖边 \((u,v)\),我们给 \(d_s\) 加 \(1\),给 \(d_v\) 减 \(1\)。对 \(d\) 做一次子树和 \(cov\),然后再求出根链上有多少边满足 \(cov_{(p,fa_p)}\leq 1\land cut_{fa_p}=0\),计算答案的时候同样差分一下即可。
这部分实现时,可以通过维护 DFS 栈得到 \(v\) 在 \(u\) 方向上的儿子 \(s\),从而代替倍增。这样我们就可以 \(\mathcal{O}(n)\) 解决这部分。
树边
这部分比较困难。
设我们删除的树边为 \((u,fa_u)\)。可以注意到,对答案有贡献的点要么在 \(sub_u\) 中,要么是 \(fa_u\) 的祖先。这是因为删去 \((u,fa_u)\) 只会影响到计算 \(low\) 时路径经过这条边的那些点,那么显然这个点要和 \(u,fa_u\) 构成祖先链。
继续分类讨论产生贡献的新的割点 \(x\) 的位置。
\(x\) 是 \(fa_u\) 的祖先
设 \(y\) 为 \(x\) 在 \(u\) 方向上的儿子。考虑把 \(x\) 和 \((u,fa_u)\) 从图中删去后,把整张图分为三个部分:\(y\) 子树外、\(y\) 子树去掉 \(u\) 子树和 \(u\) 子树。我们把它们依次称为上、中、下三个部分。
这里明确一下上部分的定义,更确切地,它应该是指 \(x\) 的所有不是 \(y\) 的儿子子树,和 \(x\) 子树外的部分。由于 \(x\) 最初不是割点,所以不难发现这两块应当是连通的,因此我们把它们划为一个部分。
\(x\) 起初不是割点,因此 \(sub_y\) 中必然有返祖边连向上部分。而删去 \((u,fa_u)\) 后 \(x\) 要成为割点,因此中部分和下部分中,有且仅有一个部分有返祖边连向上部分。
-
中部分中有返祖边连向上部分:也就是下部分和中、上部分不连通。但是树边都不是割边,所以下部分中肯定有连出下部分的返祖边,为什么删去 \((u,fa_u)\) 就会导致上下不连通呢?仔细思考可以发现,此时一定是所有下端点在 \(sub_u\) 内,上端点在 \(u\) 的祖先处的返祖边,上端点都为 \(x\),这样没了树边的连接后,\(x\) 自然就成为了割点。
-
下部分中有返祖边连向上部分:也就是中部分和上、下部分不连通。
首先,中部分怎么和下部分不连通?这是简单的,只需要保证所有从 \(sub_u\) 内连出去的返祖边的上端点的深度 \(\leq dep_x\) 即可。
那中部分如何和上部分不连通?其实就是对于每条下端点在 \(sub_y\) 内、上端点为 \(x\) 的祖先的返祖边,当我们试图从中部分向下走到某个下端点时,会被删除的那条树边挡住。更直接地刻画这个条件:考察所有上端点为 \(x\) 的祖先,下端点在 \(sub_y\) 内的返祖边,我们设这些返祖边的下端点的 LCA 为 \(d\),那么删除的树边必然在 \(y\) 到 \(d\) 的路径上。
怎么实现呢?由于维护的东西比较类似,这里一并包含了下面一种 case 要维护的东西。
一个看上去比较难维护的东西是:对每条树边 \((u,fa_u)\),求出所有下端点在 \(sub_u\) 内,上端点为 \(u/fa_u\) 的祖先的返祖边的下端点的 LCA。我们利用点集 LCA 的经典结论:
因此考虑维护所有符合条件的返祖边的下端点的 \(dfn\) 的最小值/最大值。考虑每条返祖边 \((u,v)\) 对这个值的影响,发现就是把 \(u\) 到 \(v\) 的路径上的点(实际上可能不会包括最浅的一两个点)的答案和 \(dfn_u\) 做 \(\operatorname{chkmin}/\operatorname{chkmax}\)。不妨把所有返祖边按照 \(dfn_u\) 从小到大/从大到小排序,这样就会变成覆盖之后答案不会再改变。此时我们可以用树上并查集维护,每次跳到祖先中最深的没被覆盖的点修改答案即可。
可以发现我们还需要对于每个点 \(u\),求出下端点在 \(sub_u\) 内,上端点为 \(u/fa_u\) 的祖先的返祖边中,最浅/最深的上端点。每条返祖边的影响还是相当于把一条祖先链对某个值 \(\operatorname{chkmin}/\operatorname{chkmax}\),同样用树上并查集维护即可。预处理上面这些值已经足够了。
容易发现上文章提及的两种情况是独立的。第一种情况是容易的,注意判从 \(sub_u\) 内连上去的点不能是 \(fa_u\) 且原来不是割点即可。
对于第二种情况,把形如“删除的树边必然在 \(y\) 到 \(d\) 的路径上”的限制挂到 \(y\) 上,把每条树边 \((u,fa_u)\) 挂在从 \(sub_u\) 内连出去的返祖边的最深的上端点上,按照深度从大到小排序。考虑差分,我们在 DFS 序上维护一个 BIT,对于每条限制,我们在 \(dfn_d\) 处单点 \(+1\),在 \(dfn_y\) 处单点 \(-1\),询问时查询 \(sub_u\) 对应的 DFS 序区间和即可。注意加入限制时需要保证 \(fa_y\) 原先不是割点。
\(x\) 在 \(sub_u\) 内
这里 \(x\) 要有贡献就不能为 \(u\)。然后还是考虑把整个图分为上、中、下三个部分:\(u\) 子树外、\(u\) 子树去掉 \(x\) 子树、\(x\) 的所有儿子子树。
显然上、中部分在删去 \((u,fa_u)\) 后必然不连通,否则这条树边删去与否并不会带来影响。类比前面的做法,考察所有下端点在 \(sub_u\) 内,上端点为 \(u\) 的祖先的返祖边,设这些返祖边的下端点的 LCA 为 \(d\),那么 \(x\) 必然在 \(u\) 到 \(d\) 的路径上,但不包括 \(u\)。
接下来考虑下部分,可以发现 \(x\) 为割点的充要条件是对于它的每个子树,其要么只与上部分连通,要么只与中部分连通(由于 \(x\) 起初不是割点,所以不能是和上、中部分都不连通)。依次处理 \(x\) 的每个儿子 \(s_i\),考察所有下端在 \(sub_{s_i}\) 中,上端点为 \(x\) 的祖先的返祖边,设这些返祖边的上端点中的最浅深度为 \(l\),最深深度为 \(r\),那么这就限制了 \(dep_u\notin [l+1,r]\)。于是对于每个点 \(x\),我们可以得到 \(\mathcal{O}(deg_x)\) 个深度区间,表示 \(dep_u\) 不能落在这些区间中。
来考虑实现。对于每条树边,我们想要查询 \(u\) 到 \(d\) 不包括 \(u\) 的路径上能作为新的割点的数量,显然要差分成根链询问,然后离线下来挂到点上。我们在深度上维护一棵 BIT,每次 DFS 到一个点 \(x\) 时求出 \(\mathcal{O}(deg_x)\) 个限制区间,对这些区间做区间并使得区间之间无交,然后对于每个区间在 BIT 上区间 \(+1\),离开时撤销。询问时我们单点查询 \(dep_u\),就可以得到这个点被覆盖了多少次,也就是其对应的根链上不合法的点数,用当前深度减去不合法的点数就是合法的点数了。貌似有用支持区间加、区间最小值个数的线段树维护 DFS 序的做法,我太菜了,不太懂是什么意思。
综合上述讨论,我们就可以 \(\mathcal{O}(n\log{n})\) 地解决这个问题了。
代码
写得比较丑陋,放个链接。