P8456 「SWTR-8」地地铁铁

- Upd on 2023.7.31：更换为更简单的证明。 ## [P8456「SWTR-8」地地铁铁](https://www.luogu.com.cn/problem/P8456) ### 题目描述 给定一张 $n$ 个点，$m$ 条边的无向图。每条边标有 `D` 或 `d`。 定义无序点对 $(x, y)$ 是「铁的」，当且仅当 $x \neq y$ 且 $x, y$ 之间存在同时出现 `D` 和 `d` 的简单路径。 对「铁的」点对计数。 - 简单路径定义为不经过重复 **节点** 的路径。 - 保证图无自环，连通，可能有重边。 ### 数据范围 - Subtask #1（6 points）：$n \leq 8$，$m \leq 21$。 - Subtask #2（16 points）：$n\leq 15$，$m\leq 822$。依赖 Subtask #1。 - Subtask #3（17 points）：$m = n - 1$。 - Subtask #4（18 points）：$m = n$。 - Subtask #5（19 points）：$n\leq 1064$，$m\leq 10 ^ 4$。依赖 Subtask #2。 - Subtask #6（24 points）：无特殊限制。依赖 Subtask #3，#4，#5。 对于 $100\%$ 的数据： - $2\leq n \leq 4\times 10 ^ 5$，$n - 1\leq m\leq 10 ^ 6$。 - $1\leq x, y\leq n$。 - $c\in \{\texttt{D}, \texttt{d}\}$。 - 保证图无自环，连通，可能有重边。 ### Sol 补集转化变成不存在同时出现 `D`（$1$）和 `d`（$0$）的简单路径。 如果点对之间不存在同时出现 $01$ 的路径，只有以下三种情况： - 只有 $0$ 路径。 - 只有 $1$ 路径。 - 同时有 $0$ 路径和 $1$ 路径。 接下来的推导需多次应用以下基本事实： > **性质 $1$**：对于点数 $\geq 3$ 的点双，任给两点 $x\neq y$，存在经过 $x, y$ 的简单环。 > > **证明**：点双基本性质。若 $x, y$ 不直接相连，由 [门杰定理](https://baike.baidu.com/item/门杰定理/19137908) $k = 2$ 的特殊情形可证。若 $x, y$ 直接相连，若删去 $(x, y)$ 后 $x, y$ 不连通，不妨设 $x$ 所在连通块大小 $\geq 2$，则 $x$ 为原图割点，矛盾，因此删去 $(x, y)$ 后 $x, y$ 连通，从而得到经过 $x, y$ 的简单环。$\square$ #### Part 1 对于只有 $0$ 路径的情况，考虑点双 $B$，猜测若存在 $1$ 边则经过 $B$ 的点对不合法。 > **性质 $2$**：对于点数 $\geq 3$ 的点双，任给一点 $x$ 与一边 $e$，存在经过 $x, e$ 的简单环。 > > **证明**：将 $e = (u, v)$ 拆成 $(u, w)$ 和 $(w, v)$ 不影响 $B$ 点双连通性。据性质 $1$，存在经过 $x, w$ 的简单环。因 $w$ 仅与 $u, v$ 相连，故 $(u, w), (w, v)$ 在环上，将其替换为 $(u, v)$ 可得经过 $x, e$ 的简单环。$\square$ - 不影响点双连通性的证明：删去 $u$ 或 $v$，因 $w$ 与 $v$ 或 $u$ 连通且 $B$ 删去 $u$ 或 $v$ 后连通可知 $u, v$ 不是割点；删去 $u, v, w$ 以外的点时，将 $(u, w)$ 和 $(w, v)$ 视为 $(u, v)$，$B$ 连通；删去 $w$ 相当于删去 $(u, v)$，若图不连通则 $(u, v)$ 在 $B$ 上为割边，当点数 $\geq 3$ 时 $u$ 或 $v$ 在 $B$ 上为割点，矛盾，故 $B$ 连通。 > **性质 $3$**：对于点数 $\geq 3$ 的点双，点双内任给两点 $x\neq y$ 与一边 $e$，存在 $x \to e \to y$ 的简单路径。 > > **证明**：由性质 $2$，存在经过 $x, e$ 的简单环 $C$，若 $y\in C$ 则成立，否则令 $P$ 为任意 $y\to x$ 路径，考虑 $P$ 与 $C$ 的第一个交点 $z$，存在使得 $z \neq x$ 的 $P$，否则 $x$ 为割点：删去 $x$ 后 $y$ 无法到达 $C$ 剩余节点。令 $Q = y \to z$ 接上 $z$ 通过环上有 $e$ 的一侧到 $x$ 的路径，则 $Q$ 为 $x \to e\to y$ 的简单路径。$\square$ 令 $e$ 为 $1$ 边，对点双内任意两点 $x\neq y$ 应用性质 $3$，结合 $|B| = 2$ 的平凡情况，得 > **结论 $1$**：若点双内存在 $1$ 边，则经过该点双的点对不合法。 因此，删去有 $1$ 边的点双内部所有边，剩余连通块大小选 $2$ 之和即为所求。 对于只有 $1$ 路径的情况同理。 #### Part 2 同时有 $0$ 路径和 $1$ 路径的点对是本题重点，下称「合法点对」。 > **结论 $2$**：若两点之间存在割点，则不合法。 > > **证明**：设 $x, y$ 间存在割点 $z$。考虑 $x\to z$ 和 $z\to y$ 的所有路径，它们仅在 $z$ 处相交，否则与 $z$ 为割点矛盾。若同时存在 $0$ 路径 $P_0$ 和 $1$ 路径 $P_1$，将 $P_0$ 在 $x\to z$ 的部分和 $P_1$ 在 $z\to y$ 的部分相接得到 $01$ 路径，不合法。$\square$ 可以推出合法点对属于相同点双，考虑点双 $B = (V, E)$，感性猜测 $B$ 内部最多有一对合法对。 接下来证明该结论。 考虑合法点对 $x, y$。令 $x\to y$ 所有 $0$ 路径覆盖点集 $V_0$，所有 $1$ 路径覆盖点集 $V_1$。 > **结论 $3.1$**：除 $x, y$ 以外，$V_0$ 与 $V_1$ 无交。 > > **证明**：若有交，则可通过 $P_0$ 与 $P_1$ 第一个交点调整得到 $01$ 路径。$\square$ > **结论 $3.2$**：$V_0$ 与 $V_1$ 之间无边。 > > **证明**：若有边 $u\to v$ 满足 $u\in V_0, v\in V_1$，则 $x\to u \to v \to y$ 为 $01$ 路径。$\square$ > **性质 $4$**：对于点数 $\geq 3$ 的点双，任给不同三点 $x, y, z$，存在经过 $x, y, z$ 且以 $x, y$ 为端点的简单路径。 > > **证明**：考虑以 $z$ 为端点的边 $e$。由性质 $3$，存在 $x\to e\to y$，因此存在 $x\to z\to y$。$\square$ > **结论 $3.3$**：$V_0 \cup V_1 = V$。 > > **证明**：对任意 $z\neq x, y$ 应用性质 $4$。$\square$ 考虑 $z\in V_0$，$z'\in V_0$ 且 $(x, y) \neq (z, z')$。 > **结论 $4$**：存在 $x, y$ 分别到 $z, z'$ 或 $z', z$ 的两条仅经过 $V_0$ 的不交路径。 > > **证明**：若 $z$ 或 $z'$ 与 $x$ 或 $y$ 相等，显然。 > > 否则考虑仅经过 $V_0$ 的路径 $P = x\to z\to y$。若 $z'\in P$，显然。 > > 否则考虑 $z'\to y$ 的任意路径 $Q$。考虑 $Q$ 上与 $P$ 的第一个交点 $p$。总存在 $Q$ 使得 $p\neq z$，否则删去 $z$ 后 $z'$ 无法到达 $P$。 > > 若 $p$ 在 $x\to z$ 上，则 $x\xrightarrow{P} p \xrightarrow{Q} z'$ 和 $z\xrightarrow{P} y$ 无交点。 > > 若 $p$ 在 $z\to y$ 上，则 $x\xrightarrow{P} z$ 和 $z'\xrightarrow{Q} y$ 无交点。$\square$ 因此，对于任意 $z, z' \in V_0 \land (x, y) \neq (z, z') \land z\neq z'$，存在 $x, y$ 分别到 $z, z'$ 或 $z', z$ 的两条仅经过 $V_0$ 的不交路径。将这两条路径通过 $x, y$ 之间的全 $1$ 路径连起来，得 $z, z'$ 之间不合法。 同理，对于任意 $z, z' \in V_1 \land (x, y) \neq (z, z') \land z\neq z'$，$z, z'$ 之间不合法。 而 $z\in V_0$，$z'\in V_1$ 且 $(x, y) \neq (z, z')$ 之间显然不合法。 综上，$S$ 内部最多有一对合法对。 考虑充要条件，其等价于点双内恰好存在两个点满足同时有 $01$ 出边。 充分性：考虑令唯二的两个点分别为 $x, y$。根据性质 $4$，考虑任意 $x\to u\to y$，路径必然纯色，否则考虑切换颜色的点，该点同时存在 $01$ 出边。因 $x, y$ 同时有 $0, 1$ 出边，故存在全 $0$ 路径和全 $1$ 路径。 必要性：当 $x, y$ 合法时，根据结论 $3.2$ 可知仅有 $x, y$ 同时有 $01$ 出边。 问题在 $\mathcal{O}(n + m)$ 的时间内解决。