自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:39:14，当前版本为作者最后更新于2022-08-04 11:08:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

• Upd on 2023.7.31：更换为更简单的证明。

P8456「SWTR-8」地地铁铁

题目描述

给定一张 $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$ 不直接相连，由 门杰定理 $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)$ 的时间内解决。