总算学会了...NOIp2018之前就开始学了...模板一直过不去...

需要先学会。

现在切入正题。

LCT的概况

一种数据结构。(废话)

可以均摊\(O(logn)\)维护一个森林,支持的树上任意路径的查询,两棵树的连接、断开,单点的修改。

LCT的实现基于Splay。

大概长成下面这样↓

(图片来自,下同)

LCT中的边分为实边和虚边,每一个节点连向它的孩子的边中只有一条实边。

实边需要记录在这条边的两个端点上(即孩子记父亲,父亲记孩子),虚边只需要记录在孩子上(即孩子记父亲即可)。

其中实边(实线的边)连接的一组点构成一个Splay,大小依据为深度。

Splay的根的父亲指针指向这棵Splay中深度最小的节点在原树中的父亲(这是一条虚边)。

比如上面这个LCT的Splay长这样(当然和Splay的形态没关系)↓

具体操作

LCT中的Splay必须维护的是翻转标记,其他的视题目而定。

首先是一个前置操作,判断点\(y\)是否是Splay的根(因为即使是Splay的根也可能有在别的Splay中有父亲,所以并不是没有父亲的才是根):

bool Isroot(int x){    int y=t[x].f;    return !(t[y].c[0]==x||t[y].c[1]==x);}

本文的Splay节点定义如下:

struct node{    int f,c[2],tag,...;    //f是父亲,c[0/1]是左/右孩子,tag是翻转标记}t[Size];

Splay的操作有些会有所修改,如下:

上/下传(并没有不一样):

void Upd(int x){//视具体情况而定    //something...}void Psd(int x){//主要是下传翻转标记    if(t[x].tag){        swap(t[x].c[0],t[x].c[1]);        if(t[x].c[0])t[t[x].c[0]].tag^=1;        if(t[x].c[1])t[t[x].c[1]].tag^=1;        t[x].tag=0;    }}

旋转:

void Rotate(int x){    int y=t[x].f,z=t[y].f;    Psd(y);    Psd(x);    int c=t[y].c[1]==x;    if(!Isroot(y)){//注意这里要判断y是否为Splay的根(否则z可能在另一颗Splay中或者不存在)        int gc=t[z].c[1]==y;        t[z].c[gc]=x;    }    t[x].f=z;    t[y].c[c]=t[x].c[c^1];    t[t[x].c[c^1]].f=y;    t[x].c[c^1]=y;    t[y].f=x;    Upd(y);    Upd(x);}

伸展:

void Splay(int x){    Psd(x);    while(!Isroot(x)){//这里同上        int y=t[x].f,z=t[y].f;        if(Isroot(y))Rotate(x);        else{            Psd(z);            Psd(y);            int c=t[y].c[1]==x,gc=t[z].c[1]==y;            if(c==gc)Rotate(y);            else Rotate(x);            Rotate(x);        }    }}

接下来终于开始讲LCT了

1.访问操作\(Access(x)\)

使\(x\)与当前LCT的根存在由实边组成的路径,并且\(x\)是路径中深度最大的点。

之后所有操作的基础。

我们从\(x\)开始,一路向父亲寻找,每次将节点伸展为所在Splay的根,将该节点的父亲的所有连向儿子的边变成虚边,将该节点的父亲和节点本身的边变成实边(该节点是其父亲的右儿子,因为深度大于它的父亲)。

当然为了保证\(x\)是深度最大的,一开始要把\(x\)的右儿子断开。

我个人喜欢递归实现,调用方式为\(Access(x,0)\)。

code:

void Access(int x,int lst){    if(!x)return;    Splay(x);    t[x].c[1]=lst;    Upd(x);    Access(t[x].f,x);}

2.换根操作\(Makeroot(x)\)

将\(x\)换为LCT的根。

我们需要\(Access(x)\),此时\(x\)与LCT的根直接相连,而且是它到根的路径上深度最大的。

我们要让它变成根,就是路径中深度最小的点,怎么办?

直接翻转Splay不就好了。。。

为了确定翻转标记标记的位置,我们再将\(x\)换为所在Splay的根。

code:

void Makeroot(int x){    Access(x,0);    Splay(x);    t[x].tag^=1;}

3.??操作\(Split(x,y)\)

难以概括的操作。。。就是将\(x\)到\(y\)的路径提取出来方便询问。

将\(x\)换为LCT的根,再\(Access(y)\),就得到了\(x\)到\(y\)的路径。

再\(Splay(y)\),就可以在\(y\)节点上获取路径信息了。

code:

void Split(int x,int y){    Makeroot(x);    Access(y,0);    Splay(y);}

4.找根操作\(Findroot(x)\)

找到\(x\)所在LCT的根,主要用于判断两点联通性。

先\(Access(x)\),将\(x\)和它在LCT中的根放在同一个Splay中,再\(Splay(x)\),将\(x\)变为所在Splay的根。

然后\(x\)所在LCT的根必然是深度最小的,所以一直跳左孩子即可。

(记得下传标记哦)

code:

int Findroot(int x){    Access(x,0);    Splay(x);    Psd(x);    while(t[x].c[0]){        x=t[x].c[0];        Psd(x);    }    Splay(x);//维持Splay的平衡    return x;}

5.连接操作\(Link(x,y)\)

在\(x,y\)之间连一条边。

首先如果\(x,y\)已经联通(\(Findroot(x)=Findroot(y)\)),操作不合法,直接退出即可。

否则,让\(x\)成为所在LCT的根,将它和\(y\)之间连一条虚边(即让\(x\)的父亲为\(y\))。

code:

void Link(int x,int y){    Makeroot(x);    if(Findroot(y)!=x)t[x].f=y;}

6.断边操作\(Cut(x,y)\)

断开\(x\)和\(y\)之间的边(如果有的话)。

\(Makeroot(x)\)后,\(x\)是LCT的根,而\(y\)深度必然大于\(x\),所以会在右子树中,深度相差1(如果存在这条边),即在Splay中\(x\)的右孩子。

如果\(y\)和\(x\)直接连边,那么首先判断联通性,然后看看\(y\)是否是\(x\)的右孩子,并且\(y\)没有左孩子(如果有左孩子说明\(x\)和\(y\)之间还有点)。

存在的话直接断边就好了。

code:

void Cut(int x,int y){    Makeroot(x);    Psd(x);    if(Findroot(y)==x&&t[y].f==x&&!t[y].c[0]){        t[x].c[1]=t[y].f=0;        Upd(x);    }}

结束。

最后给出模板题代码:

#include
    
     using namespace std;struct node{    int f,c[2],v,xs,tag;}t[300010];int n,m,op,u,v;void PrintLCT(){    for(int i=1;i<=n;i++){        cout<
     
      <<"<-node "<
      <<" l->"<
       
        <<" r->"<
        
         <<"\n";    }}bool Isroot(int x){    int y=t[x].f;    return !(t[y].c[0]==x||t[y].c[1]==x);}void Upd(int x){    t[x].xs=t[x].v^t[t[x].c[0]].xs^t[t[x].c[1]].xs;}void Psd(int x){    if(t[x].tag){        swap(t[x].c[0],t[x].c[1]);        if(t[x].c[0])t[t[x].c[0]].tag^=1;        if(t[x].c[1])t[t[x].c[1]].tag^=1;        t[x].tag=0;    }}void Rotate(int x){    int y=t[x].f,z=t[y].f;    Psd(y);    Psd(x);    int c=t[y].c[1]==x;    if(!Isroot(y)){        int gc=t[z].c[1]==y;        t[z].c[gc]=x;    }    t[x].f=z;    t[y].c[c]=t[x].c[c^1];    t[t[x].c[c^1]].f=y;    t[x].c[c^1]=y;    t[y].f=x;    Upd(y);    Upd(x);}void Splay(int x){    Psd(x);    while(!Isroot(x)){        int y=t[x].f,z=t[y].f;        if(Isroot(y))Rotate(x);        else{            Psd(z);            Psd(y);            int c=t[y].c[1]==x,gc=t[z].c[1]==y;            if(c==gc)Rotate(y);            else Rotate(x);            Rotate(x);        }    }}void Access(int x,int lst){    if(!x)return;    Splay(x);    t[x].c[1]=lst;    Upd(x);    Access(t[x].f,x);}void Makeroot(int x){    Access(x,0);    Splay(x);    t[x].tag^=1;}void Split(int x,int y){    Makeroot(x);    Access(y,0);    Splay(y);}int Findroot(int x){    Access(x,0);    Splay(x);    Psd(x);    while(t[x].c[0]){        x=t[x].c[0];        Psd(x);    }    Splay(x);    return x;}void Link(int x,int y){    Makeroot(x);    if(Findroot(y)!=x)t[x].f=y;}void Cut(int x,int y){    Makeroot(x);    Psd(x);    if(Findroot(y)==x&&t[y].f==x&&!t[y].c[0]){        t[x].c[1]=t[y].f=0;        Upd(x);    }}int Query(int x,int y){    Split(x,y);    return t[y].xs;}void Change(int x,int y){    Splay(x);    t[x].v=y;    Upd(x);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++){        scanf("%d",&t[i].v);        t[i].xs=t[i].v;    }    for(int i=1;i<=m;i++){        scanf("%d%d%d",&op,&u,&v);        if(op==0)printf("%d\n",Query(u,v));        else if(op==1)Link(u,v);        else if(op==2)Cut(u,v);        else Change(u,v);    }    return 0;}