简介

LCT是一种数据结构, 可以维护树的动态加边, 删边, 维护链上信息(满足结合律), 单次操作时间复杂度 \(O(\log n)\).(不会证)

思想类似树链剖分, 因为splay可以换根, 用splay维护重链, splay的中序遍历即为链按深度从小到大遍历的结果.

操作

注意区分splay和整棵树的区别, splay根和树根的区别.

\(Access(p)\) 操作指的是将p与根放在同一棵splay中.

\(MakeRoot(p)\) 操作指的是将p变为它所在树(而不是splay)的根. 由于维护的是链上信息, 这不会对答案产生影响.

\(FindRoot(p)\) 操作指的是求p所在树(而不是splay)的根.

\(Link(x,y)\) 操作指的是如果p与q不在同一棵树中, 那么连边 \((x,y)\).

\(Cut(x,y)\) 操作指的是如果p与q有边相连, 那么连边 \((x,y)\).

其中, 'p与q有边相连' 等价于同时满足:

- p,q在同一棵树中.

- p,q深度相差1.(splay中p,q中序遍历时相邻)

\(Split(x,y)\) 操作指的是取出 \((x,y)\) 这个链, 并放在一棵splay中.

具体实现见代码.

应用

• 动态树(代替树链剖分)
• 动态最小生成树
• 维护子树信息(AAA树)
• 维护并查集(e.g. 可持久化并查集)
• 优化dinic(据tarjan论文)(怕不是会写死)

Code

const int nsz=3e5+50;int n,val[nsz];struct tlct{    struct tnd{int ch[2],fa,sum,rv;}tree[nsz];#define ls(p) tree[p].ch[0]#define rs(p) tree[p].ch[1]#define fa(p) tree[p].fa#define dir(p) (rs(fa(p))==p)    bool isrt(int p){return ls(fa(p))!=p&&rs(fa(p))!=p;}//splay rt    void rev(int p){swap(ls(p),rs(p));tree[p].rv^=1;}    void pu(int p){        tree[p].sum=tree[ls(p)].sum^val[p]^tree[rs(p)].sum;    }    void pd(int p){        if(tree[p].rv==0)return;        if(ls(p))rev(ls(p));        if(rs(p))rev(rs(p));        tree[p].rv=0;    }    void pdt(int p){//push down whole splay; from top to bottom        if(!isrt(p))pdt(fa(p));        pd(p);    }    void rotate(int p){//fa(p) should exist        int x=fa(p),y=fa(x),dir1=dir(p),dir2=dir(x),z=tree[p].ch[dir1^1];        if(!isrt(x))tree[y].ch[dir2]=p;fa(p)=y;        tree[p].ch[dir1^1]=x;fa(x)=p;        tree[x].ch[dir1]=z;if(z)fa(z)=x;        pu(x),pu(p);//can't swap    }    void splay(int p){        pdt(p);        while(!isrt(p)){            if(!isrt(fa(p)))rotate(dir(p)==dir(fa(p))?fa(p):p);            rotate(p);        }    }    void access(int p){        for(int y=0;p;y=p,p=fa(p)){            splay(p),rs(p)=y;            pu(p);        }    }    void makert(int p){//p -> tree rt & splay rt        access(p),splay(p);        rev(p);    }    int findrt(int p){//find tree rt; p -> splay rt        access(p),splay(p);        while(ls(p))pd(p),p=ls(p);        splay(p); //不加会tle... 不知道为什么        return p;    }    bool iscon(int x,int y){return findrt(x)==findrt(y);}    void split(int x,int y){//x -> tree rt; y -> splay rt        makert(x);        access(y);        splay(y);    }    void link(int x,int y){        makert(x);        if(findrt(y)!=x)fa(x)=y;    }    void cut(int x,int y){        split(x,y);        if(fa(x)==y&&rs(x)==0)            fa(x)=ls(y)=0,pu(y);    }    void pr(){        rep(i,1,n)printf("nd=%d fa=%d ls=%d rs=%d sum=%d rv=%d\n",i,fa(i),ls(i),rs(i),tree[i].sum,tree[i].rv);    }}lct;//initrep(i,1,n)tree[i].sum=val[i];//query a chain    lct.split(b,c);    ans=lct.tree[c].sum;//modify one point    lct.makert(b);    val[b]=c;    lct.pu(b);