LCT总结（个人笔记）

# LCT总结 -------- >前置技能：$splay$ ### 介绍： LCT即 Link-Cut-Tree， 其中Link指连接，Cut指断开，Tree则是一棵树。 说白了就是一棵**动态树**， 可以**动态删除边，添加边。** 擅长处理**链上的问题**， 但是**子树问题**也可以解决，后面会有例题。 ----- 当然，作为一个优秀的数据结构$LCT$， 肯定不能像普通的树一样暴力跳父亲， 肯定要有优秀的方法快速找根。 但普通的树是用 **倍增** 和 **重链剖分**。 >_(或许还有**长链剖分**_ 而这两种算法都不能修改。 所以我们用的是另一种方法：**实链剖分** ----- ## 实链剖分 ------- 这里先介绍一下什么是 **实链剖分** 。 实际上就是选一个儿子与自己的边当做**实边**， 其他边都是**虚边** >实边需要满足什么条件？ >实边不需要任何条件， >就是自己随便选的， >就是因为是随便选的，所以才可以**动态连边删边**。 这些实边就形成了实链。 _当然也可以都是虚边_ ------- 我之前在一篇博客里面看到一句话， 很好的概括了实边和虚边的区别： >认子不认父 即每个点**不用管自己和父亲连的是实边还是虚边**， 只要记录**与哪一个儿子连实边**就行了。 如果需要判断自己和父亲是不是连实边 只需要判一下**父亲的实儿子**是不是自己就行了 >感觉有什么怪怪的？？？ ----- 那么有了实链之后有什么用？ 怎么把实链用在$LCT$上？ >想一下如果是重链剖分的话，应该怎么找根呢？ 我们可以一直跳到实链的顶端，直到到达根为止。 但是这样还有几个问题需要解决： 1. 怎么保证跳的实链的次数不会过大？ 2. 怎么跳到每条链的顶端的父亲？ ----- #### 第一个问题：怎么保证跳的实链的次数不会过大？ 我们可以每次把当前的点和根变成一条实链， 以此来保证复杂度的合理性。（感性理解） ### 第二个问题：怎么跳到每条链的顶端的父亲？ 重链剖分里面是直接记录每一个点的$top$指向哪里。 而实链剖分就不能这么做，因为$top$随时可能会变。 这时候就要用到最核心的知识了， **把每一条实链用一个splay来表示**： 1. **左儿子**深度都比当前点**浅** 2. **右儿子**深度都比当前点**深** splay当中最左边的数就是链的顶端了。 但，链顶的点不一定是splay的根怎么办？ 即，可能链顶的点的$fa$表示的是**splay**当中的$fa$ 我们注意到，$splay$当中，根是没有父亲的。 所以我们可以这么做， 每个$splay$的根的$fa$表示**链顶的点在树中的父亲** ------ 做个图以便理解：  _其中加粗的是实边，其他的是虚边。_ 而实际上每一个实链是用**splay**来表示的， 所以可能实际上$son$和$fa$的关系是这样的。  其中每一个框就是一个$splay$ ------ >？**mmp**为什么写了半天的概念 接下来就是怎么设计代码了。 $up,down$ 以及 $pushr$(翻转)与普通$splay$一样。 多了一个判断是不是$splay$的根的函数$noroot$ ```cpp bool noroot(int x){ return son[fa[x]][0]==x||son[fa[x]][1]==x; }//如果不是splay的根返回true; ``` 首先，LCT当中的$splay$的$rotate$和$splay$ 是不能复制普通$splay$的， **有些不同。** ### rotate操作 ```cpp void rotate(int x){ int y=fa[x]; int z=fa[y]; int k=(son[y][1]==x); if(noroot(y))son[z][(son[z][1]==y)]=x; fa[x]=z; son[y][k]=son[x][k^1]; fa[son[x][k^1]]=y; son[x][k^1]=y; fa[y]=x; up(y);up(x); } ``` 为什么需要判断$noroot(y)$呢？ 因为如果$y$是根则说明$z$不在$x$这个$splay$内 如果不加则会改变$z$的**实儿子**，故错。 ------ ### splay操作 ```cpp void splay(int x){ int u=x,top=0; stk[++top]=u; while(noroot(u))stk[++top]=u=fa[u]; while(top)down(stk[top--]); //即先down完之后再splay while(noroot(x)){ int y=fa[x]; int z=fa[y]; if(noroot(y)) (son[z][1]==y)^(son[y][1]==x)?rotate(x):rotate(y); rotate(x); } } ``` ---- 以上都是处理实链的操作，那么怎么造出实链呢？ 下面这个操作就是$LCT$的核心操作了。 ### access操作 ```cpp void access(int x){ for(int y=0;x;y=x,x=fa[x]) splay(x),son[x][1]=y,up(x); } ``` 这段代码什么意思呢？ 即造出$x$到$root$这条实链，之前的其他实边变为虚边。 循环里面是把$x$与$y$连上实边，之前的实边被覆盖。 1. $splay(x)$：把x旋转到根 2. $son[x][1]=y$：之前的实边被覆盖，实儿子变成y。 注意链是从$root$到$x$的， 所以$x$实际上位于**实链的最底端，$splay$的最右端。** ------- 接下来的代码想想就都能明白了 ### makeroot操作 ```cpp void makeroot(int x){ access(x);splay(x);pushr(x); } ``` 把$x$变成树的根。 ------- ### findroot操作 ```cpp int findroot(int x){ access(x);splay(x); while(son[x][0])down(x),x=son[x][0]; splay(x);//保证复杂度 return x; } ``` 还有一个操作可以把要修改的链给拎出来 ### split操作 ```cpp void split(int x,int y){ makeroot(x);access(y);splay(y); //直接对y节点进行询问即可 } ``` 最后就是连边和删边操作了 ### link操作 所连的边可能已经存在了，那么这么写 ```cpp bool link(int x,int y){ makeroot(x); if(findroot(y)==x)return false; fa[x]=y;//直接连接虚边 return true; } ``` 如果数据中保证边合法，那么可以这么写 ```cpp void link(int x,int y){ makeroot(x); fa[x]=y; } ``` ----- ### cut操作 所删的边可能不存在，需要这么写 ```cpp bool cut(int x,int y){ makeroot(x); if(findroot(y)!=x||fa[y]!=x||son[y][0])return false; son[x][1]=fa[y]=0; up(x); return true; } ``` 如果数据中保证边合法，那么可以这么写 ```cpp void cut(int x,int y){ split(x,y); son[y][0]=fa[x]=0; up(y); } ``` ------- 那么$LCT$基本就已经讲完了，接下来就是做题经验了。 ### LCT在基环树当中的应用 基环树当中有一个环，但显然树里面不能有环， 所以可以用$LCT$把基环树变成树。 即把环中的一个点变成根， 再把连成环的那条边单独记录下来， 如果环被破坏掉了则连回去。 [LCT专题L](https://cn.vjudge.net/contest/282972#problem/L) ### LCT维护子树信息 $LCT$实际上也可以维护子树的信息 只不过略微麻烦一点， 就是多维护一个虚儿子的信息， 在$access$的时候注意修改就行了。 [LCT专题K](https://cn.vjudge.net/contest/282972#problem/K) ------ END