Policija 题解

思路

两类询问分别对应删除一条边和删除一个点后的连通性。对连通无向图建立一棵深度优先搜索树，记录每个点的发现时间、子树区间以及低链接值。

若一条询问道路不是搜索树边，它一定不构成桥。若它是父子边，设较深端点为 $x$，当且仅当 $low_x>dfn_{fa_x}$ 时该边是桥。删除桥后，$x$ 的搜索树子树与其余顶点分离，因此只需判断 $A,B$ 是否同时位于该子树中。

删除城市 $C$ 时，$C$ 的某个搜索树儿子 $y$ 的整棵子树会独立分离，当且仅当 $low_y\ge dfn_C$。其余儿子子树仍能通过返祖边连到 $C$ 的祖先一侧，属于同一个剩余连通块。对任意城市 $x\ne C$，若 $x$ 不在 $C$ 的子树中，则它属于剩余连通块；否则用倍增找到 $C$ 到 $x$ 路径上的第一个儿子 $y$，再根据 $low_y$ 判断 $x$ 所属的连通块。$A,B$ 的块标识相同即仍然连通。

做法

使用显式栈完成深度优先搜索，避免长链导致递归栈溢出。搜索过程中计算 $dfn$、$low$、父亲、深度和子树结束时间，并建立二进制倍增父亲表。

第一类询问先判断给定道路是否为搜索树父子边，再判断它是否为桥；只有桥需要比较两个城市是否位于同一侧。

第二类询问分别求出 $A,B$ 在删除 $C$ 后的连通块标识。标识为零表示祖先侧或能通过返祖边接回祖先侧，其他标识使用对应的分离儿子编号。

正确性证明

在无向图的深度优先搜索树中，父子边 $(p,x)$ 是桥，当且仅当 $x$ 的子树没有到达 $p$ 或其祖先的返祖边，即 $low_x>dfn_p$。因此删除非桥不改变连通性；删除桥后恰好分成 $x$ 子树和其余顶点两侧，第一类询问的判定正确。

删除点 $C$ 后，对它的搜索树儿子 $y$，若 $low_y\ge dfn_C$，则 $y$ 子树无法绕过 $C$ 到达 $C$ 的祖先侧，也无法到达另一个这样的儿子子树，因而形成独立连通块。若 $low_y<dfn_C$，该子树存在通向 $C$ 祖先的返祖边，与所有祖先侧顶点连通。算法给每个顶点分配的块标识正好对应这些连通块，所以两个城市标识相同当且仅当删除 $C$ 后仍连通，第二类询问的判定正确。

复杂度分析

预处理时间复杂度为 $O((N+E)\log N)$，空间复杂度为 $O((N+E)\log N)$。每个第一类询问为 $O(1)$，每个第二类询问为 $O(\log N)$，总时间复杂度为 $O((N+E+Q)\log N)$。