P8456 「SWTR-8」地地铁铁

· · 题解

P8456「SWTR-8」地地铁铁

题目描述

给定一张 n 个点，m 条边的无向图。每条边标有 D 或 d。

定义无序点对 (x, y) 是「铁的」，当且仅当 x \neq y 且 x, y 之间存在同时出现 D 和 d 的简单路径。

对「铁的」点对计数。

数据范围

对于 100\% 的数据：

Sol

补集转化变成不存在同时出现 D（1）和 d（0）的简单路径。

如果点对之间不存在同时出现 01 的路径，只有以下三种情况：

接下来的推导需多次应用以下基本事实：

性质 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

性质 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) 的时间内解决。