动态树中，是指不断地使用splay树的功能对辅助树的结构等进行更改从而进行更优的操作，并利用splay减少时间复杂度的算法。 LCT的性质：

  1. 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。 ~是不是有点抽象哈~ 比如有一棵树，根节点为11（深度1），有两个儿子2,32,3（深度2），那么Splay有33种构成方式： {1−2},{3}{1−2},{3} {1−3},{2}{1−3},{2} {1},{2},{3}{1},{2},{3}（每个集合表示一个Splay） 而不能把1,2,31,2,3同放在一个Splay中（存在深度相同的点）
  2. 每个节点包含且仅包含于一个Splay中
  3. 边分为实边和虚边，实边包含在Splay中，而虚边总是由一棵Splay指向另一个节点（指向该Splay中中序遍历最靠前的点在原树中的父亲）。 因为性质2，当某点在原树中有多个儿子时，只能向其中一个儿子拉一条实链（只认一个儿子），而其它儿子是不能在这个Splay中的。 那么为了保持树的形状，我们要让到其它儿子的边变为虚边，由对应儿子所属的Splay的根节点的父亲指向该点，而从该点并不能直接访问该儿子（认父不认子）。
  • c[x][0]代表这个节点的父节点集合，以及父节点往上的节点
  • c[x][1]代表这个节点的子节点集合，以及子节点往下的节点
  • 实边：父亲认儿子，儿子认父亲
  • 虚边：儿子认父亲，父亲不认儿子
  • LCT是利用splay维护中序遍历，在同一颗LCT树中，中序遍历不变，并且利用splay的特性，把LCT变矮变胖，使得深度变浅，优化了时间复杂度（但实际上并不一定特别优，可以根据实际情况维护更多的信息，比如 [SDOI2017] 树点涂色多维护了深度最浅节点编号）
  • rotate（x）：旋转x和他的父亲
void rotate(int x)  //旋转
{
  int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
  if( nroot(y) ) c[z][c[z][1]==y]=x;  //如果y不是当前splay的根的话才去旋转x到上面
  c[x][!k]=y;c[y][k]=w;
  if( w ) f[w]=y;  //如果x反方向儿子存在才去更新父亲
  f[y]=x;f[x]=z;   
  pushup(y);  //旋转后更新y的值
  pushup(x);  //x更新
}
  • splay（x）：保证树的中序遍历不变的同时将树压扁，并将x节点旋转到当前树上的根，具体操作为不断旋转x和他的父亲，直到无法旋转为止
void splay(int x)
{
int y=x,z=0;
st[++z]=y;
while( nroot(y) ) st[++z]=y=f[y];
while(     z    ) pushdown(st[z--]);
while( nroot(x) )
{
y=f[x],z=f[y];
if( nroot(y) )
rotate( (c[y][0]==x)^(c[z][0]==y)?x:y );
rotate(x);
}
pushup(x);
}

  • access（x）：打通x节点到当前的根节点，具体操作为 一直splay当前x节点到当前树的根上，然后旋转完后把之前的点接在当前位置上，实现实链和虚链的转化

    void access(int x)
{
for(int y=0;x;x=f[y=x]) splay(x),rc=y,pushup(x);
}

  • findroot(x)：找当前x节点的根，打通x节点并旋转到根节点后，一直找左儿子，（有的题可能会卡这里，此时需要维护深度最前的节点编号c[x][0]）

    int findroot(int x)
{
access(x);splay(x);
while( lc ) pushdown(x),x=lc;
splay(x);
return x;
}

  • makeroot(x) ：将x旋转到根节点上，具体操作为：1.打通x到根节点的树，2.将x节点旋转到根节点，3.翻转左右儿子（因为x为根节点的话，x是不应该有比x深度更浅的点的，也就是x的左儿子应该为空，而splay后x的左儿子存在右儿子消失，所以需要翻转左右儿子）

    void makeroot(int x)
{
access(x);splay(x);
pushr(x);
}

  • split(x,y) ：将x和y节点单独作为一棵splay树，具体操作为，使x为当前树的根（保证了去掉x往上的节点），然后打通y到根节点（x节点）的路径，最后旋转y到根节点就可以了，这样y以下的节点就会被splay掉

    void split(int x,int y)
{
makeroot(x);
access(y);splay(y);
}

  • link(x,y) ：链接x、y这一条路径，让x为当前节点的根，并且y所在的splay的根不是x就可以直接将x的父亲定义为y就可以实现链接边的操作

    void link(int x,int y)
{
makeroot(x);
if( findroot(y)!=x ) f[x]=y;
}

  • cut(x,y) ：删除x、y之间的边，具体操作为，让x成为当前树的根，并且y的父亲和根都是x节点，就可以断开

    void cut(int x,int y)
{
makeroot(x);
if( findroot(y)==x and f[y]==x and !c[y][0] )
{
f[y]=c[x][1]=0;
pushup(x);
}
}

完整代码

#include<bits/stdc++.h>
#define lc c[x][0]
#define rc c[x][1]
using namespace std;
const int SZ=1<<19,N=3e5+12;
int f[N],c[N][2],v[N],s[N],st[N];
bool r[N];
inline bool nroot(int x)
{
  return c[f[x]][0]==x || c[f[x]][1]==x;  //判断x是不是当前splay的根
}
void pushup(int x)
{
  s[x]=s[lc]^s[rc]^v[x];  //更新值，s位置上的异或和等于左儿子异或右儿子异或本身
}
void pushr(int x)
{
  int t=lc;
  lc=rc;rc=t;r[x]^=1;  //下放lazy需要做的事情：左右儿子互换，标记更新
}
void pushdown(int x)
{
  if( r[x] )
  {
    if( lc ) pushr(lc);  //左儿子更新
    if( rc ) pushr(rc);  //右儿子更新
    r[x]=0;     //标记归零
  }
}
void rotate(int x)  //旋转
{
  int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
  if( nroot(y) ) c[z][c[z][1]==y]=x;  //如果y不是当前splay的根的话才去旋转x到上面
  c[x][!k]=y;c[y][k]=w;
  if( w ) f[w]=y;  //如果x反方向儿子存在才去更新父亲
  f[y]=x;f[x]=z;   
  pushup(y);  //旋转后更新y的值
  pushup(x);  //x更新
}
void splay(int x)
{
  int y=x,z=0;
  st[++z]=y;
  while( nroot(y) ) st[++z]=y=f[y];
  while(     z    ) pushdown(st[z--]);
  while( nroot(x) )
  {
    y=f[x],z=f[y];
    if( nroot(y) )
      rotate( (c[y][0]==x)^(c[z][0]==y)?x:y );
    rotate(x);
  }
  pushup(x);
}
void access(int x)
{
  for(int y=0;x;x=f[y=x]) splay(x),rc=y,pushup(x);
}
void makeroot(int x)
{
  access(x);splay(x);
  pushr(x);
}
int findroot(int x)
{
  access(x);splay(x);
  while( lc ) pushdown(x),x=lc;
  splay(x);
  return x;
}
void split(int x,int y)
{
  makeroot(x);
  access(y);splay(y);
}
void link(int x,int y)
{
  makeroot(x);
  if( findroot(y)!=x ) f[x]=y;
}
void cut(int x,int y)
{
  makeroot(x);
  if( findroot(y)==x and f[y]==x and !c[y][0] )
  {
    f[y]=c[x][1]=0;
    pushup(x);
  }
}
int main(){
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    cin>>v[i];
  }
  while(m--)
  {
    int type,x,y;
    cin>>type>>x>>y;
    if( type==0 ) split(x,y),cout<<s[y]<<endl;
    if( type==1 ) link(x,y);
    if( type==2 ) cut(x,y);
    if( type==3 ) splay(x),v[x]=y;
  }
}

题目

来自FlashHu大佬的题目推荐,并把部分内容切换至本OJ上

  1. 维护链信息（LCT上的平衡树操作）

  1. 动态维护连通性&双联通分量（可以说是并查集的升级，因为并查集只能连不能断）

  1. 维护边权（常用于维护生成树）

维护边权是真抽象啊

  1. Language
  2. Legacy mode
  3. Theme
  5. 渝ICP备2024027573号-2
  8. Worker 0, 46ms
  9. Powered by Hydro v5.0.0-beta.13 Community