LCT小记
command_block
2020-04-11 18:03:03
# LCT本体
LCT是维护**动态森林**的数据结构。
支持 : 连边，断边，换根，提取路径等等操作。是一个强大的数据结构。
首先我们先来看基本原理 : **实链剖分**。
或许你听说过重链剖分，那是维护静态树路径的利器，但是这里是动态的，所以固定的剖分方式容易出锅。
实链剖分就是一种动态的剖分方式，随着操作自适应地剖。具体咋剖可看下文。
注意 : `LCT` 的具体实现是经过**精细设计**的。所以要先接受一些钦定和假设,最终才能顺利地讲述算法流程。
我们把剖出来的链条用平衡树维护，**链上的点以深度为序**。
这里绝大多数时候要使用`Splay`，因为精细设计，只有与`Splay`才能配合默契。请先熟悉`Splay`的基本操作。
我们如何将若干条链组合成一棵树呢? 我们令链的`Splay`根节点指向**整条链**在原树中的父亲，而这个父亲并不记录这个儿子，即“**认父不认子**”。
下面给出一些`Splay`相关操作，注意一些特殊的细节。
可以看到维护了翻转标记，有什么用后面再说。
```cpp
struct Node{
int l,r,f,s,x;bool fl;
inline void ladd()
{fl^=1;swap(l,r);}
}a[MaxN];
inline bool nrt(int u)
{return a[a[u].f].l==u||a[a[u].f].r==u;}
inline void up(int u)
{a[u].s=a[a[u].l].s^a[a[u].r].s^a[u].x;}
inline void ladd(int u){
if (a[u].fl){
a[a[u].l].ladd();
a[a[u].r].ladd();
a[u].fl=0;
}
}
inline void rot(int u)
{
int fa=a[u].f,gf=a[fa].f;
ladd(fa);ladd(u);
a[a[fa].f=u].f=gf;
if (a[gf].l==fa)a[gf].l=u;
if (a[gf].r==fa)a[gf].r=u;
//记住要写成两个if,不然会出现0有儿子的情况
if (a[fa].l==u){
a[a[fa].l=a[u].r].f=fa;
a[u].r=fa;
}else {
a[a[fa].r=a[u].l].f=fa;
a[u].l=fa;
}up(fa);up(u);
}
int st[MaxN],tn;
void splay(int u)
{
int v=u;tn=0;
for (;nrt(v);v=a[v].f)st[++tn]=v;
st[++tn]=v;
for (int i=tn;i;i--)ladd(st[i]);
//先将路径上的所有标记推走
while(nrt(u)){
int fa=a[u].f,gf=a[fa].f;
if (nrt(fa)&&((a[gf].l==fa)==(a[fa].l==u)))
rot(fa);
rot(u);
}
}
```
- `Access` 操作
**作用** : 将根到 $u$ 的路径提取到一个`Splay`中。
这个操作是 `LCT` 的精华部分和关键。
现在的情况如下图 :
第一步，我们要先切断 $u,v$ 之间的重边，把链分成两段。如下图:
具体操作就是把 $u$ 旋到根，然后让比 $u$ 更深的右侧子树“另立门户”。
然后，来到 $u$ 这条链的父亲 $v$ ，我们要把这条链打通。如下图:
首先，要把 $v$ 更深的链除去，方法同上。
然后 $v$ 在 `Splay` 的根部，右儿子是空的，正好放下 $u$ ，则合为一条链。
然后发现已经到达整棵树的根 $R$ ，停止操作。
代码出奇的简洁:
```cpp
void access(int u)
{
for (int v=0;u;v=u,u=a[u].f){
splay(u);
a[u].r=v;up(u);
}
}
```
解释一下。首先 `splay(x)` ，把当前重链划分成两半。
然后把 $x$ 的右儿子(更深处)**替换**成上一层的重链顶，此时原来的岔路成为了“干儿子”。
然后对 $x$ 的信息进行更新，将 $y$ 记录为 $x$ (上一层重链顶)，跳跃至下一条重链。
这也回答了上面“怎么剖”的问题。
事实上，这样看似乱剖，其实每次剖时相当于在到根的链上做`splay`。
累加势能即可得到和单棵`Splay`类似的结果 : 均摊 $O(\log n)$。
这个模型也同样可以迁移到其他的题目，比如 [P6292 【模板】区间本质不同子串个数](https://www.luogu.com.cn/problem/P6292)
- `Makeroot` 操作
**作用** : 将 $u$ 置为当前树的根。
我们来思考祖先关系是由什么表示的，答案是“认父不认子”和“按深度排序”两个体系。
我们先执行 `access(u)` ，然后 $u$ 和当前根就只按“按深度排序”规则来管理祖先关系了。
现在，把整棵树翻转，相当于把这一条链的父边方向反转了， $u$ 就变为了根。
代码同样十分简洁:
```cpp
void makrt(int u)
{access(u);splay(u);a[u].ladd();}
```
- `Spilt`操作
**作用** : 将 $u,v$ 之间的路径整理到同一个 `Splay` 中，并以 $v$ 为平衡树根。
首先令 $u$ 为整棵树的根，打通 $y$ 与根之间的路径,最后 `splay(v)` 即可。
```cpp
void spilt(int u,int v)
{makrt(u);access(v);splay(v);}
```
- `Findroot`操作
**作用** : 查询 $u$ 所在的树的树根。
前面讲到过，祖先关系的表示比较复杂，所以找根也略微有点复杂。
同样先执行 `access(u)` ，然后在当前 `Splay` 中找到最浅点即可，别忘记推懒标记。
找到了之后需要 `splay(u)` 一下，否则复杂度可能退化。
```cpp
int findrt(int u)
{
access(u);splay(u);
while(a[u].l){ladd(u);u=a[u].l;}
splay(u);return u;
}
```
- `Link`操作
**作用** : 在当前森林中连边 $u\leftrightarrow v$。
先执行 `makert(u)` ，让 $u$ 能够代表整个联通块，然后令 $u$ 认 $v$ 为“干爹”即可。
注意，如果此时 `findrt(v)=u` ，则表示 $u,v$ 本就在同一连通块内，无需操作。
```cpp
void link(int u,int v)
{
makrt(u);
if (findrt(v)==u)return ;
a[u].f=v;
}
```
- `Cut`操作
**作用** : 在当前森林中删去边 $u\leftrightarrow v$。
首先执行 `spilt(u,v)` ，如果 $u,v$ 在原树中直接连接，此时 $v$ 的**左**子树中一定**有且只有** $u$ ，否则这条边不存在。
否则让 $u,v$ 之间断绝一切父子关系即可。记得更新 $v$ 的信息。
```cpp
void cut(int u,int v)
{
spilt(u,v);
if (a[v].l!=u||a[u].l!=a[u].r)return ;
a[v].l=a[u].f=0;up(v);
}
```
复杂度为 $O\big((n+m)\log n\big)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 105000
using namespace std;
int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
struct Node{
int l,r,f,s,x;bool fl;
inline void ladd()
{fl^=1;swap(l,r);}
}a[MaxN];
inline bool nrt(int u)
{return a[a[u].f].l==u||a[a[u].f].r==u;}
inline void up(int u)
{a[u].s=a[a[u].l].s^a[a[u].r].s^a[u].x;}
inline void ladd(int u){
if (a[u].fl){
a[a[u].l].ladd();
a[a[u].r].ladd();
a[u].fl=0;
}
}
inline void rot(int u)
{
int fa=a[u].f,gf=a[fa].f;
a[a[fa].f=u].f=gf;
if (a[gf].l==fa)a[gf].l=u;
if (a[gf].r==fa)a[gf].r=u;
if (a[fa].l==u){
a[a[fa].l=a[u].r].f=fa;
a[u].r=fa;
}else {
a[a[fa].r=a[u].l].f=fa;
a[u].l=fa;
}up(fa);up(u);
}
int st[MaxN],tn;
void splay(int u)
{
int v=u;tn=0;
for (;nrt(v);v=a[v].f)st[++tn]=v;
st[++tn]=v;
for (int i=tn;i;i--)ladd(st[i]);
while(nrt(u)){
int fa=a[u].f,gf=a[fa].f;
if (nrt(fa)&&((a[gf].l==fa)==(a[fa].l==u)))
rot(fa);
rot(u);
}
}
void access(int u)
{
for (int v=0;u;v=u,u=a[u].f){
splay(u);
a[u].r=v;up(u);
}
}
void makrt(int u)
{access(u);splay(u);a[u].ladd();}
int findrt(int u)
{
access(u);splay(u);
while(a[u].l){ladd(u);u=a[u].l;}
splay(u);return u;
}
void spilt(int u,int v)
{makrt(u);access(v);splay(v);}
void link(int u,int v)
{
makrt(u);
if (findrt(v)==u)return ;
a[u].f=v;
}
void cut(int u,int v)
{
spilt(u,v);
if (a[v].l!=u||a[u].l!=a[u].r)return ;
a[v].l=a[u].f=0;up(v);
}
int n,m;
int main()
{
n=read();m=read();
for (int i=1;i<=n;i++)a[i].x=read();
for (int i=1,ord,u,v;i<=m;i++){
ord=read();u=read();v=read();
if (ord==0){spilt(u,v);printf("%d\n",a[v].s);}
if (ord==1)link(u,v);
if (ord==2)cut(u,v);
if (ord==3){splay(u);a[u].x=v;up(u);}
}return 0;
}
```
- **易错点**
- `rot(u)` 中连父边的双 `if`。
- `splay(u)` 中双旋一定要确定不是根，因为 `rot(u)` 不能对根使用。
- `access` 中的 $y$ 初值一定要赋为 $0$ 。
- 该 `access` 要 `access` (统一平衡树),该 `splay` 要 `splay` (代表整棵树)
- `findrt` 里面的推标记。
- `link/cut` 里面无用操作的判据(头脑清醒应该不会错)
- **调试方法**
`LCT` 的有效部分长度仅为 `1.3Kb` ，我花了 `10min` 就写完了。
但是代码虽简洁，却很难调，后面的时间都用在调试上了。
- **静态查错** : 比较推荐的方法，毕竟代码短，看的东西不多，对照常犯的错误检查即可。
- **动态查错** :
这些函数是层层嵌套的，所以要先快速找到断点，麻烦的是断点之间还有因果关系，要不断回溯。
一般来讲，如果写挂了，小数据就会锅，一个比较方便的方法是输出全部点的连接信息。
而且，切莫以为某个函数写对了，就不需要调试信息。往往底层函数的调试信息更能揭示因果关系。
- **机器查错** : 有些时候样例太水，过了仍然很慌咋办……
某些题目需要转化后使用 `LCT` ，这时建议先单独对 `LCT` 调试而不是大杂烩。
`LCT` 挂的形式一般表现为死循环或者 `RE` ，这就不需要对拍了。
如果还是想拍，写个邻接矩阵 `DFS` 似乎不错，反正数据不需要太大。
说句闲话，我的代码毫无复杂的卡常，比大多数正常写法的人都短，似乎在模板里面跑得挺快?
现在洛谷评测机有和当年性能差，旧的提交记录更快，排到了最优解第一页……(瞻仰论文哥)
此外， `LCT` 在某种程度上比树剖好写 (对于静态树无需 `link/cut` 更好写) ，所以可以在部分题目中代替树剖，特别是细节多的题目。
- **例题①** [P1501 [国家集训队]Tree II](https://www.luogu.com.cn/problem/P1501)
`LCT` $\times$ [P3373 【模板】线段树 2](https://www.luogu.com.cn/problem/P3373)
简单推标记练习，熟悉板子。
- **例题②** [P2173 [ZJOI2012]网络](https://www.luogu.com.cn/problem/P2173)
同样近乎于模板题，对每种颜色开一个`LCT`维护即可。
- **进阶题** [P3703 [SDOI2017]树点涂色](https://www.luogu.com.cn/problem/P3703)
好的性质题，每次从 $u$ 到根染上新颜色这个设定一看就很像 `access`。
观察到每个点到根的轻边个数，发现正好等于颜色个数，因为颜色是不会交替出现的。
每次切换轻重边，就对受到影响的子树在 `dfs` 线段树上操作。
对于操作 `2` ，由于 $V$ 字形路径的两个岔路必然不包含相同的颜色，可以直接累加。
答案即为 $dep[u]+dep[v]-2*dep[lca(u,v)]+1$ ，最后要 $+1$ 是因为算上 $lca$ 本身的颜色。
对于操作 `3` ，取一个子树最大值即可。
# LCT维护子树
前文只提到了 `LCT` 维护路径，然而在维护子树上似乎比较无力。
事实上，借助一些技巧，我们还是能维护一些子树信息的。(但是不能修改)
注意到，我们丢失了子树信息，根本原因是我们使虚边“认父不认子”。
我们考虑维护一个“虚子树和”，即所有虚边儿子的权值和，这只需要在 `access/link` 里面修改，在 `Splay` 上可以视作这个点的“附加权值”来维护。
进行 `access` 时，我们会有更换右儿子的操作，这时我们要把 $u$ 原来的右儿子的 LCT 子树信息加入 $u$ 的虚子树信息，把 $u$ 的新的右儿子的 LCT 子树信息从 $u$ 的虚子树信息中除去。这要求**贡献可逆**。
进行 `link` 时，我们会先把点 $u$ 置为根,然后连一条 $u$ 到 $v$ 的虚边，这时我们发现不仅 $v$ 的虚子树信息需要加入 $u$ 的 LCT 子树信息， $v$ 的所有祖先的 LCT 子树信息也需要更改。
我们先提前对 $v$ `access` 再 `splay` 就行了，这样子单独修改 $v$ 即可。
进行 `cut` 时，我们会先提出 $(u,v)$ 的路径，此时断开的是实边所以无需改动。
注意，由于 `Splay` 的求和，我们并不能任意取用子树和，而必须要 `splay(u)` 之后去掉左子树更浅的贡献。
- **例题** [P4219 [BJOI2014]大融合](https://www.luogu.com.cn/problem/P4219)
查询边的负载，实际上就是边两侧点数的乘积。
对于边 $(u,v)$ ，我们先 `makert(u)` 。
$u$ 的点数$=$总点数- $v$ 的点数。
重要之处都在代码里 `mark` 出来了。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 100500
using namespace std;
inline int read(){
register int X=0;
register char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
inline char readc(){
register char ch=0;
while(ch<'A'||ch>'Z')ch=getchar();
return ch;
}
int n,m;
struct Node{
int l,r,c,pc,f;
bool tr;
inline void rev()
{tr^=1;swap(l,r);}
}a[MaxN];
inline void up(int u)
{a[u].c=a[a[u].l].c+a[a[u].r].c+a[u].pc+1;} //mark
inline void ladd(int u){
if (a[u].tr){
a[a[u].l].rev();
a[a[u].r].rev();
a[u].tr=0;
}
}
inline bool nrt(int u)
{return a[a[u].f].l==u||a[a[u].f].r==u;}
inline void rot(int u)
{
int fa=a[u].f,gf=a[fa].f;
ladd(fa);ladd(u);
if (a[gf].l==fa)a[gf].l=u;
if (a[gf].r==fa)a[gf].r=u;
a[a[fa].f=u].f=gf;
if (a[fa].l==u){
a[a[fa].l=a[u].r].f=fa;
a[u].r=fa;
}else {
a[a[fa].r=a[u].l].f=fa;
a[u].l=fa;
}up(fa);up(u);
}
void splay(int u)
{
ladd(u);
while(nrt(u)){
int fa=a[u].f,gf=a[fa].f;
if (!((a[fa].l==u)^(a[gf].l==fa))&&nrt(fa))rot(fa);
rot(u);
}
}
void access(int x)
{
for (int y=0;x;x=a[y=x].f){
splay(x);
a[x].pc=a[x].pc+a[a[x].r].c-a[y].c; //mark
a[x].r=y;
up(x);
}
}
void makrt(int x)
{access(x);splay(x);a[x].rev();}
void spilt(int x,int y)
{makrt(x);access(y);splay(y);}
void link(int x,int y)
{
spilt(x,y); //mark
a[a[x].f=y].pc+=a[x].c; //mark
up(y);
}
char ord;
int main()
{
n=read();m=read();
for (int i=1;i<=n;i++)a[i].c=1;
for (int i=1,x,y;i<=m;i++){
ord=readc();x=read();y=read();
if (ord=='A'){
link(x,y);
}else {
int cx,cy;
makrt(x);splay(x);cx=a[x].c;
access(y);splay(y);cy=a[y].c-a[a[y].l].c; //mark
printf("%lld\n",1ll*(cx-cy)*cy);
}
}return 0;
}
```
[评测记录](https://www.luogu.com.cn/record/32701939)
然而这题没有断边，似乎被很多其他奇怪的解法弄过去了。
- **例题②** [P5212 SubString](https://www.luogu.com.cn/problem/P5212)
本题需要动态维护 `SAM` 的 `edp` 。
发现 `edp` 就是子树内后缀点数的和，所以维护虚子树和就可以了。
注意到 `SAM` 中连边断边都是父亲和儿子之间的，那么可以不写 `makert` ，不用推标记，常数会小很多。
有一个坑点是开头的串是不需要解密的。
[评测记录](https://www.luogu.com.cn/record/32717576)
- **进阶题①** [SP16549 QTREE6 - Query on a tree VI](https://www.luogu.com.cn/problem/SP16549)
**题意** : 给出一棵黑白树，资瓷反转颜色，求某个点的同色联通块大小。
容易想到每种颜色维护一个 `LCT` ，直接按照两端颜色是否相同来维护边。但是遇到菊花图就被卡飞了。
考虑把颜色放到边上，某条边存在当且仅当**深度大**的一端颜色对劲。
这样，同色联通块在顶端会多出一个点。这里需要给原树加入一个虚根避免特判。
可能通过这个点连接了许多“相邻”的同色联通块。所以我们要通过 `findrt` 找到这个点，然后只取需要的那个儿子。
我们要维护父子顺序，就不能用 `makert` 了 (同时也不需要翻转标记了)。
`link/cut` 要根据只会连接父边的性质实现，注意该 `splay` 的时候就 `splay`。
[评测记录](https://www.luogu.com.cn/record/32719582)
- **进阶题②** [SP16580 QTREE7 - Query on a tree VII](https://www.luogu.com.cn/problem/SP16580)
**题意** : 给出一棵黑白树，资瓷反转颜色，求某个同色联通块的最大值。
和上一题差不多，仍然是子树信息，只不过信息不可减。
我们对每个点使用一个可删堆维护虚子树信息即可，这样复杂度是 $O(n\log^2 n)$ 的。
注意这里对信息的加删极为严格。
[评测记录](https://www.luogu.com.cn/record/33725628)
- **进阶题③** [P4299 首都](https://www.luogu.com.cn/problem/P4299) & [[DS记录]P4299 首都](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p4299-shou-du)
混合了一些图论(重心)的知识。需要 `Splay` 上二分。
## LCT维护生成树
首先我们来看看 `LCT` 如何动态加边维护最小生成树。
每加一个边，相当于在原来的最小生成树上形成了一个环。
我们查看这个环上的最大权值，如果比当前边大，则替换。根据 Kruskal 算法不难证明其正确性。
这里需要维护边权而非点权，可以使用虚点装边权，真正的点点权为 $0$ 即可，这样子常数是原来的两倍。
- [P4172 [WC2006]水管局长](https://www.luogu.com.cn/problem/P4172) 这个题时间倒流一下就是模板了。
- **例题①** [P2387 [NOI2014]魔法森林](https://www.luogu.com.cn/problem/P2387)
**题意** : 给出一个无向图，每条边有两种权值，求一条 $1\leftrightarrow n$ 的路径，使得两种权值的最大值的和最小。
- 一道类似的题目 : [P4234 最小差值生成树](https://www.luogu.com.cn/problem/P4234)
首先按照 $a$ 权值排序，依次加边，维护 $b$ 权值的最小生成树，然后用当前 $a+b$ 更新答案即可。
`findrt` 判连通性常数较大，对于这种只会合并的题目，可以用并查集判断连通性。
[评测记录](https://www.luogu.com.cn/record/18541271)
```cpp
#include<algorithm>
#include<cstdio>
#define Pr pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define MaxN 100500
using namespace std;
inline int read(){
register int X=0;
register char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
struct Node{
int l,r,f;
Pr x,s;bool tr;
inline void rev()
{tr^=1;swap(l,r);}
}a[MaxN];
inline void up(int u)
{a[u].s=max(max(a[a[u].l].s,a[a[u].r].s),a[u].x);}
inline void ladd(int u){
if (a[u].tr){
a[a[u].l].rev();
a[a[u].r].rev();
a[u].tr=0;
}
}
inline bool nrt(int u)
{return a[a[u].f].l==u||a[a[u].f].r==u;}
inline void rot(int u)
{
int fa=a[u].f,gf=a[fa].f;
ladd(fa);ladd(u);
if (a[gf].l==fa)a[gf].l=u;
if (a[gf].r==fa)a[gf].r=u;
a[a[fa].f=u].f=gf;
if (a[fa].l==u){
a[a[fa].l=a[u].r].f=fa;
a[u].r=fa;
}else {
a[a[fa].r=a[u].l].f=fa;
a[u].l=fa;
}up(fa);up(u);
}
void splay(int u)
{
ladd(u);
while(nrt(u)){
int fa=a[u].f,gf=a[fa].f;
if (!((a[fa].l==u)^(a[gf].l==fa))&&nrt(fa))rot(fa);
rot(u);
}
}
void access(int x){
for (int y=0;x;x=a[y=x].f){
splay(x);
a[x].r=y;up(x);
}
}
void makert(int x)
{access(x);splay(x);a[x].rev();}
void spilt(int x,int y)
{makert(x);access(y);splay(y);}
void link(int x,int y)
{makert(x);a[x].f=y;}
void cut(int x,int y)
{
spilt(x,y);a[x].f=a[y].l=0;up(y);}
struct Line
{int f,t,a,b;}l[MaxN],s[MaxN/2];
int tl;
bool cmp(const Line &A,const Line &B)
{return A.a<B.a;}
int f[MaxN];
int findf(int u)
{return f[u]==u ? u : f[u]=findf(f[u]);}
void merge(int x,int y)
{f[findf(x)]=findf(y);}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)f[i]=i;
for (int i=1;i<=m;i++){
l[i].f=read();l[i].t=read();
l[i].a=read();l[i].b=read();
}int ans=1<<30;
sort(l+1,l+m+1,cmp);
for (int i=1,x,y;i<=m;i++){
x=l[i].f;y=l[i].t;
if (x==y)continue;
int tp=0;
if (findf(y)==findf(x)){
spilt(x,y);
tp=a[y].s.sec;
if (s[tp].b<=l[i].b)continue;
cut(s[tp].f,tp+n);
cut(tp+n,s[tp].t);
}if (!tp){tp=++tl;merge(x,y);}
s[tp]=l[i];
a[tp+n].x=a[tp+n].s=mp(s[tp].b,tp);
link(x,tp+n);link(tp+n,y);
if (findf(1)==findf(n)){
spilt(1,n);
ans=min(ans,l[i].a+a[n].s.fir);
}
}printf("%d\n",ans==(1<<30) ? -1 : ans);
return 0;
}
```
- **例题②** [P4230 连环病原体](https://www.luogu.com.cn/problem/P4230)
**题意** : $n$ 个点的无向图，给出边的序列 $A[1...m]$。
如果连接上 $A[l...r]$ 之后产生任意一个环，则称 $[l,r]$ 是好的。
对于每个好的 $[l,r]$ ，将 $c[l...r]$ 加 $1$ ，最后询问 $c$ 数组。
考虑尺取法，枚举右端点，做端点尽量缩直到没有环为止,设此时缩到了 $[l,r]$.
那么 $[[1...l),r]$ 这些区间都是好区间。对 $c$ 数组的影响是加一个等差序列。
拿个二阶差分搞一搞便可。
[评测记录](https://www.luogu.com.cn/record/33777575)
- **例题③** [P4319 变化的道路](https://www.luogu.com.cn/problem/P4319)
**题意** : 给出一张无向图，资瓷加边删边维护最小生成树。允许离线。
前面我们讲的是加边维护最小生成树，这里需要删边，弄一个线段树分治即可。
注意，虽然 `LCT` 的复杂度是均摊的，但是 `LCT` 有删除操作可以用于回退，所以复杂度是正确的$O(n\log^2n)$。
[评测记录](https://www.luogu.com.cn/record/33777575) (常数大得不可思议)
- **进阶题①** [P5385 [Cnoi2019]须臾幻境](https://www.luogu.com.cn/problem/P5385)
**题意** : $n$ 个点的无向图，给出边的序列 $A[1...m]$。
每次询问仅连接上 $A[l...r]$ 之后整个图的连通块个数。强制在线。
第一眼看上去，这和动态生成树并没有什么关系，我们挖掘一下性质。
首先有 $\text{连通块数}=\text{点数}-\text{生成树边数}$。
令第 $i$ 条边的权值为 $i$。
考虑使用边 $A[l...r]$ 的情形，此时 $(u,v)$ 不连通**当且仅当** :
- $A[1...r]$ 的**最大生成树**上 $(u,v)$ 之间的最小值小于 $l$ ，或者不连通。
所以我们只需要考虑前缀最大生成树。
这是一个常用技巧，先限定区间一端，然后把另一端当做条件。
我们使用 `LCT` 维护这个前缀最大生成树，每次记录下断掉的边，可以得出每条边的存活区间。
形式化的讲，某条边的存活区间是 $[l,r]$ ，目前的询问为 $[L,R]$.
则这条边能够贡献的条件是 : $[L\leq l\leq R][R\leq r]$ ，显然主席树二维数点即可。
[评测记录](https://www.luogu.com.cn/record/33735250)
- **进阶题②** [P5489 EntropyIncreaser 与 动态图](https://www.luogu.com.cn/problem/P5489)
考虑动态维护圆方树。
若已经得到了当前图的圆方树，则两点间割点即为圆点，两点间割边即为圆圆边。
考虑在圆方树上加边 $u\leftrightarrow v$ 会发生什么。
若 $u,v$ 本不联通，则直接连边 $u\leftrightarrow v$。
否则，会形成环，将环上的所有圆点纳入一个点双联通分量中。
将该环的所有边断开，并将所有点连接到一个新的方点上。根据势能分析，复杂度是正确的。
这样得到的“圆方树”并非一个点双只有一个方点，而是由很多方点聚合而成。
（注意，若 $u,v$ 在同一个边双联通分量中，仍然需要新建方点以减小势能）
需要用额外的点来维护圆圆边。
[评测记录](https://www.luogu.com.cn/record/47976346)