题解 P5247 【【模板】动态图完全连通性】

## 复杂度均摊的 Holm-de Lichtenberg-Thorup 分层图算法 - 我们给定每条边一个权值。保证它的上界在 $\log{n}$ ，这个值越大，就说明这条边在越多的判断中没有发挥作用。所有边一开始权值都为 $0$。那么我们就得到了分层图，所有边可以向下合并。显然，连通性只需要一颗树就可以维护，所以我们应该维护的是这个图的生成树森林。 - 定义 $G_i$ 表示所有边权大于等于 $i$ 的边构成的图，$F_i$ 表示 $G_i$ 的最大生成树。 - 那么我们不难发现: - $G_{i+1}\in G_{i}$ - $G_{i}$ 与 $F_{i}$ 的连通性相同。 - $F_{i}=G_{i}\cap F_{0}$，$F_{i}$ 一定为 $G_{i}$ 最大生成树。 ------------ 在有了以上的性质以后，我们就可以正式地开始了。 - 显然，这题难的是删边，加边和询问直接在 $G_{0}$ 操作就行。 - 而删边，如果它破坏了原有图形生成树的连通性，我们就得遍历所有可能的边，来看它是否能够重新“代替”这条边。 - 而反观 $F_{i}$ 为最大生成树的性质，所以如果有边能够“代替”这条边，那么它的权值一定小于等于当前边，否则它应该在最大生成树中。 - 在找边的过程中，我们遍历较小的树的一边的边，我们查找的每一条边，如果能够代替，就在 $F_{i}$ 中连上这条边，否则就将它的权值加 1。 - 依次查找 $G_{i},G_{i-1}...G_{0}$ 直到找出来。 - 在查找时，我们还需要 tag 来表示当前节点及其子树是否有可能更新的边，不能直接遍历子树，否则复杂度就是错误的。 ------------ - Q：听说要用 ETT，如果我不会怎么办？ - A：~~你可以学~~维护子树 LCT 好像也行，但我没有实现。 - Q： BFS 不香吗？ - A：香，怎么不香，~~但这样怎么涨社区的分呀~~。 ------------ 以下是更新内容： #### 复杂度的一些分析 ----- - 我们将图上的所有的非树边取出来。 - 设我们当前正在处理第 i 层边。 - 在每次断边的时候我们遍历小子树，将当前无用边的权值加一。 - 那么在权值更大的一层图中，两点所在的 $F_{i+1}$ 一定连通。 - 又由于当前这条边属于 $F_{i}$ 中较小的一个连通块，所以在 $F_{i+1}$ 的连通块中，当前边所在的块大小一定小于 $F_{i}$ 所在大小的一半。每一层减少一半，故分层图只需 $\log n$ 层，每条边也做多上升 $\log n$ 次。 - 在任意一个森林中我们要找到一条边(的一个端点)的复杂度均摊是 $\log n$，每条边只会被找 $\log n$ 次，所以总复杂度 $O(\log ^{2} n)$，这也是为什么要用 tag 记录是否存在边，这样上面找边的复杂度才能摊下来。 - 论文上的复杂度是 $O(\frac{\log^{2} n}{\log \log n})$，查询很简单 $O(\log n)$。 #### 维护动态树的数据结构的一些乱扯 ----- - 动态树一般指 LCT，但是在这道题当中如果使用 LCT，我们就必须要在寻找一个子树或者说虚儿子子树内的标记节点，并且仍然做到 $O(\log n)$，这就需要选手掌握较(自)为(适)高(应)深(顶)的(树) LCT 维护技巧。 - 这题对动态树的 link cut 灵活性要求比较强，不是简单地换父亲，而括号序和欧拉序都会在换根的时候打乱儿子的顺序还有自己节点出现的先后顺序。 - 我们考虑如何维护一个快速的动态树，有子树信息。 - 因为我们只需要维护连通性，即当前节点射出去的一条无向边。所以实际上来讲我们并不关心它在 ETT 有什么入或者什么出的性质，我们只关心这个点的编号，还有这条边的信息，这两个信息即可。 - 也就是说我们不论用欧拉序或者括号序换根，儿子顺序被打乱这对我们没有任何影响。我们挂边的时候直接在它所有出现的节点中随便选一个节点挂上去就行了，这样我们找边均摊仍然是 $O(\log n)$ 的，没有影响我们上面的复杂度分析。 - 所以我们可以直接用 ETT 进行维护，换根直接区间平移即可。 upd on 2021.7.23 : 修改了原算法的一些描述与增加后面的复杂度分析，还有 ETT。 ### 最后来讲一些实现问题。 有上面的结论可以的到 ETT 和 LCT 都可以，现在我们来分别讨论一下。 #### Link - Cut - Tree - 考虑 LCT 做一个子树 search 的时候，虚儿子的信息比较难进行查找。 - 我们可以考虑用一个 set 存储虚儿子中的任意一个标记点，然后上传，但是由于二叉树形分治结构的特殊性，我们得使儿子中结构不同时，传上来的却是同一个值。 - 我这里采用的是传的最小的标记节点。 - 每次做 search 的时候就暴力 access 过去，这样一定会整个连通块当中的标记点全部扫过。 - 但是注意，set 无法均摊进入 LCT 的复杂度当中。时间复杂度 $\mathcal O(n\log^{3}n)$，如果想要优化可以运用 Top Tree 的技巧优化到 $\mathcal O(n \log^{2}n)$。 - 但是这种方法一定是最好写的，没有编号的映射，没有树形结构转为线性的转化。 - [code:Link - Cut - Tree,Version](https://www.luogu.com.cn/paste/6pc21m9t) #### Euler - Tour - Tree Splay - 考虑使用 splay 对 ETT 进行维护。splay 是动态树的好般配，应该会是大多数人的第一选择。 - 但是考虑这道题上面，我们在做 search 的时候同时会进行对信息的查询，也就会遍历路径。如果要做到保证复杂度的话就一定要 **精细实现** ，也就毒瘤了亿点点，这边还是建议使用 FHQ，splay 的实现比较复杂和精细。 - [code:Euler - Tour - Tree,splay,Version](https://www.luogu.com.cn/paste/gao91hcu) #### Euler - Tour - Tree FHQ - 考虑 FHQ，它原本就有复杂度合法的高度，也就是说我们如果在遍历的时候查询信息也能同时更新。 - 在本题上实现较为方便。但是由于 ETT 自身的复杂性，还是写起来比 LCT 麻烦的多。 - [code:Euler - Tour - Tree,FHQ,Version](https://www.luogu.com.cn/paste/8oryigsf) ## 随机击中割边集合 cutset 结构做法 - 考虑我们当前所面临的的问题，仍然是如何找到一条被割掉的边的代替边。 - 首先我们来看一下下面的模型： > 给定一个图 $G(V,E)$，和图的一个连通点集 $T \subset V$，我们称 $cutset(T)$ 表示有且仅有一边端点在点集 $T$ 以内的节点的边集，我们把边集内的边称为“割边”。 > > 那么，如果**恰好**存在**一条**这样的边，那么是不是我们将边进行编号后，每个节点存储所有与他相连的边的编号异或和，$xor(T)$ 就是那条割边的编号。 - 这个方法看上去恰好击中割边的概率实在是太小了，而且受“恰好”限制。 - 首先我们考虑如何在有多条割边的情况下找到一条割边。 - 因为 $xor$ 运算就是数论性质的破坏狂魔，我们根本不能从“解密”的方面下手。那么就只有从加入边的地方下手了，我们需要维护不同的边集使得 $T$ 与外界只有一条边相连，也就是说我们要舍弃一些边的信息。 - 但是又不能真的舍弃，于是我们又考虑维护一个非均摊分层图。每一层当中的边，有二分之一的概率上升到更高一级的图层。（此处我们实现的时候手操一下 $B$ 层，$B$ 与 $\log n$ 同阶） - 那么我们就得到了一个正确性有待证明的解法： - 维护分层图，其中只维护一颗生成树用于表示树边和连通点集，那么显然非树割边就是我们要找的代替边。 - 有边加入就随一个编号，然后对于两个端点异或上去，如果两边不连通，则再加入树边。 - 有边删除就对于两个端点异或上去，如果是树边就断掉树边并执行一个查找代替边的过程（就是维护子树异或和，令子树中连通点集为 $T$）。 - 考虑查找代替边：我们显然会碰到下面三种情况。 1. $xor(T)=0$，大概率 $T$ 就独立了，没边连出去，结束查询。 2. $xor(T)=I$，（$I$ 有边的编号映射），大概率 $I$ 就是代替边，验证后结束查询。 3. $xor(T)=I$，（$I$ 无边的编号映射），那说明 $T$ 有很多条连出去的边，但是我们不能确定一条实际的边。这个时候分层图就有作用了，我们考虑在升高一层的图中去查找代替边。 - 复杂度 $O(nB\log n)$，维护连通子集需要一个维护动态树为基础的数据结构，然后 $B$ 层图每层都需要维护信息。正确性的求解过程由于笔者水平有限，具体参考 wikipedia，为 $(\frac{8}{9})^{\lg n}$，那么选取一个合适的参数 $C$ 使得 $(\frac{8}{9})^{C\lg n}$ 趋近于 $0$，得到合法方案。 - 算法的大致流程就是这样。在实现过程中需要一些较好的随机方式来解决各种随机数的冲突与分布情况。具体可以参考代码，在我的实现方法中，$C=12，B=12$ 能够通过 $luogu$ 数据，$loj$ 由于 hack 数据的存在在只改变 $B,C$ 的情况下遗憾离场，hack 数据 最快一次跑了 $22s$。 - 本算法的优点是脱离了均摊分析，将维护子树的 LCT 载体换为可持久化 ETT 即可完成可持久化动态图的完全连通性。缺点是常数巨大，空间占用较大，对随机方式要求较高。 - 优化方向： - 随机上的优化，让程序的“随机”参数更贴近理论分析。 - 结构上的优化，让 $cutset$ 结构查找割边有更高的效率和正确。 - [code:Link - Cut - Tree,cutset structure](https://www.luogu.com.cn/paste/fkoeshxy)