AT4929 [AGC033F] Adding Edges

· · 题解

本文偏理解，故不讲究完全的严谨。

以下的边均指图 G 中的边，而树边才指 T 中的边。

首先我们发现 G 中连边与在 T 中路径顺序有关，我们希望用 G 转化出性质相同的 G' 尽可能像 T 从而得到一些有利条件方便处理。

注：性质相同指可以生成相同的最终图，这里说的是转化，也就是说可能删边，但性质相同即可。

考虑一个三元组 (a,b,c)，满足以某种顺序在 T 中的一条路径上，且在 G_x 中连通，G_x 表示 G 转化到 G' 过程中的某个图。

如果有边 (a,b) 和 (b,c)，那么 (a,c) 是可以生成的，也就是说三条边最后都一定会出现，于是我们先不关心每条边原本是否出现。

考虑 (a,b,c) 在 T 路径上的顺序，如果顺次是 a,b,c：

那么两端的边 (a,c) 在 G' 中没有什么必要，而 (a,b),(b,c) 就得出现在 G' 中。

现在考虑边原本是否出现，如果 (a,b),(b,c) 中有边原本没有出现，就把它加上，可以看作是用 (a,b)/(b,c) 替换掉了 (a,c)。

那么我们直接把 (a,c) 丢掉，看 (a,b),(b,c) 中没有就补上，一直这样转化，最后生成了一个图 G'。

从 T 的角度看这个过程，每条 G_x 的边相当于是 T 的一条路径，每次把跨越了，或者说包含了，有相同端点的其他路径的路径给截成两段，如果后面一段没出现就添加那一段路径。

那么 G' 的长相应当是：很多个连通块，每条边代表 T 上的一条路径且有端点相同代表的路径在 T 上无包含，但注意，这些路径是可以有交的，只是不能包含。

充分性显然，我们可以依次连边连过去，必要性也显然，因为每种能连出来的边的连边过程按 $G'$ 的转化方法那么截最后一定对应 $G'$ 上一段路径。 我们对每个点在 $T$ 上 DFS（也可以 BFS），把 $G'$ 路径上的上一个点带着走，顺便就可以把上面的性质判断出来，于是可以做到统计答案。 如何转化 $G'$？设计一个函数 $L(x,y)$ 表示加一段 $(x,y)$ 的路径。 再设状态 $f_{x,y}$ 表示如果有 $(x,y)$ 这段路径 $x$ 会被截到哪里，初始 $f_{x,y}=x$，如果 $f_{x,y}=y$ 代表之前已经有了这样的一段路径。 函数 $L(x,y)$ 实现： - 先用 $f_{x,y},f_{y,x}$ 把 $(x,y)$ 截到最短，并标记 $f_{x,y}=y,f_{y,x}=x$，代表现在有了这样的一段路径，当然如果已经有了就退出。 - 对于端点 $x$ 预处理会怎么截后面的路径，即更新 $f_{x,z}$ 或截出后面一段路径，对端点 $y$ 同理: - 如果有包含 $(x,y)$ 的路径 $(x,z)$ 且 $f_{x,z}=x$ 表示没被截，就把它截成 $(y,z)$，即 $f_{x,z}=y$。并继续向后找路径截（起码包含了 $(x,z)$ 的其他路径，肯定也包含了 $(x,y)$）。 - 如果有包含 $(x,y)$ 的路径 $(x,z)$ 且 $f_{x,z}=p$ 一定表示是有这样一段路径，即一定有 $p=z$，因为 $(x,y)$ 已经被截得最短了。那么截掉它，调用 $L(y,z)$，表示加一段路径 $(y,z)$，不再往后找路径，因为后面一定都被 $(x,z)$ 给截掉了。 将上述所说拼成一份代码就完了，将 $n,m$ 看作同阶，则复杂度 $O(n^2)$。 复杂度分析：先考虑截短，每次加边调用一次 $L(c_i,d_i)$，令 $d=dist(c_d,d_i)$，每次截短 $d$ 都会减少，至多减少 $d$ 次，故复杂度 $O(n)$，加边截短总复杂度 $O(mn)$。 再考虑更新，$f_{x,y}$ 总共只有 $O(n^2)$ 的状态，且每个只会更新一次，故复杂度为 $O(n^2)$。 特殊的，这里有递归截短，令 $d'=(y,z)$，这样一段路径中间必定要更新 $f_{x,y},f_{x,v_1},f_{x,v_2},\dots,f_{x,v_k}(,f_{x,z})$ 这 $d'$ 个状态，故与更新复杂度相同，$O(n^2)$。 [代码](https://www.luogu.com.cn/paste/p6i2halw)：其中 $Lnk$ 函数就是题解中的 $L$ 函数。 Upd：复杂度分析。 Upd：更正了对 $L(x,y)$ 函数的一些描述。 Upd：补充了代码。