动态图连通性
再这样下去要被自己蠢死
维护一副图，支持 \(\operatorname{link,cut}\)，判断 \(x,y\) 是否在同一个联通块中
最 \(naive\) 的就是每次双端 \(\operatorname{bfs}\) 了，然后就在板子中吊打 \(O(n\log n)\) 的正解
Holm-de Lichtenberg-Thorup 算法
我们从一种实际的角度上可以有一个 \(naive\) 的想法：只要一棵树就可以维护图的连通性了，许多非树边在被删了为止都没有共享，我们考虑用 \(v_e\) 度量一条边 \(e\) 在询问中的有用程度，\(v_e\) 越大，就越不可能使用到 \(e\)。然后每次按 \(v\) 从小到大找边，可以在实际应用中优化一点常数
一个更聪明的做法是对于不同的 \(e\) 维护生成树，顺次查询
这启发我们优化 \(\operatorname{max}v_e\)，可以大胆猜测这是 \(O(\log n)\) 的
我们用 \(G_i\) 表示原图的一个子图，这个子图满足 \(v_{e\in G_i}\ge i\)
对于 \(G_0\)，我们随便维护一个生成树森林，记为 \(F_0\)，\(F_i=G_i\cap F_0\)
再定义 \(T_i\) 满足 \(v_{e\in T_i}=i\and T_i\subset F_i\)，形象化地说，\(F_0\) 是原图的一个生成树森林，\(T_i\) 是森林中权为 \(i\) 的边集
相应的，用 \(N_i\) 表示权为 \(i\) 的非树边构成的边集
只需要维护这些集合就可以解决问题了，剩下的就不用说了
判断联通性
很简单，在 \(F_0\) 上查一下就好了，用 \(\operatorname{LCT}\) 可以做到 \(O(\log n)\)
加边
在 \(F_0\) 上判一下是不是树边，如果是就插到 \(F_0\) 里，否则就插到 \(N_0\) 里
断边
首先看一下，如果是非树边的话直接删掉就好了
树边的情形会影响连通性，需要考虑其他非树边的影响，设 \(e\) 连接了 \(A,B\) 两颗子树，不妨令 \(|A|\le |B|\)
我们只需要考虑 \(A\) 的所有非树边，任意一条非树边 \(e\) 要是 \(A\) 内部的一条非树边，要么是连接 \(A,B\) 的一条非树边
对于第二种情况，我们直接重新 \(\operatorname{link}\) 回来就好了，用 \(\operatorname{LCT}\) 就可以
对于第一种情况，置 \(v_e\leftarrow v_e+1\)，直观上就是把这条边上移一层，然后因为 \(|A|\le |B|\)，这样的移动至多有 \(O(\log n)\) 层
总结
简而言之，我们维护一个 \(O(\log n)\) 层的图，每层有一颗 \(\operatorname{LCT}\) 和一个 \(\operatorname{set}\)，分别维护树边和非树边，我们需要：
- \(\operatorname{LCT}\) 的标准操作 \(\operatorname{link,cut}\)
- 把一颗 \(\operatorname{LCT}\) 和它内部的非树边全部上移一层
一条边至多被上移至 \(O(\log n)\) 层，然后被从上至下删掉，断边用 \(\operatorname{cut}\) 是 \(O(\log n)\) 的，于是一条边均摊下来就是 \(O(\log^2 n)\) 的
最后复杂度就是 \(O(m\log^2 n)\)，其中 \(n\) 是节点数，\(m\) 是操作数
标签：LCT,连通性,log,树边,动态图,非树边,operatorname,在线 From： https://www.cnblogs.com/efX-bk/p/maintain_on_a_graph.html