洛谷3690：【模板】Link Cut Tree—

洛谷3690：【模板】Link Cut Tree——题解

阅读量：6001 次

发布时间：2019-06-20

本文共 2719 字，大约阅读时间需要 9 分钟。

给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。

2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。

3：后接两个整数(x，y)，代表将点x上的权值变成y。

模板题就不说什么了。

我们多维护一个节点的key值（权值）和val值（splay中子树的异或和），每次update即可。

对于3操作我们把该节点access然后splay，更新key之后update即可。

剩下就是LCT基本操作。

UPT：18.4.2更新：

数据被加强了，多了删掉一个不存在的边导致的bug。

所以对于cut函数要多处理一遍，具体的处理方法就是打通x和y，这样x作为重链末端没有儿子，x的爸爸为y，y只有x一个儿子。

凡是不符合的即为没有该边。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int N=3e5+5;int n,m,r,fa[N],tr[N][2],rev[N],q[N],key[N],val[N];inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}inline bool get(int x){ return tr[fa[x]][1]==x;}inline bool isroot(int x){ if(!fa[x])return 1; return tr[fa[x]][0]!=x&&tr[fa[x]][1]!=x;}inline void upt(int x){ int ans=0; if(tr[x][0])ans^=val[tr[x][0]]; if(tr[x][1])ans^=val[tr[x][1]]; val[x]=key[x]^ans;}inline void pushrev(int x){ if(!rev[x])return; swap(tr[x][0],tr[x][1]); if(tr[x][0])rev[tr[x][0]]^=1; if(tr[x][1])rev[tr[x][1]]^=1; rev[x]=0;}inline void rotate(int x){ int y=fa[x],z=fa[y],which=get(x); if(z&&!isroot(y))tr[z][tr[z][1]==y]=x; tr[y][which]=tr[x][which^1];fa[tr[y][which]]=y; fa[y]=x;tr[x][which^1]=y;fa[x]=z; upt(y);upt(x);}inline void splay(int x){ q[r=0]=x; for(int y=x;!isroot(y);y=fa[y])q[++r]=fa[y]; for(int i=r;i>=0;i--)pushrev(q[i]); while(!isroot(x)){ if(!isroot(fa[x])) rotate((get(x)==get(fa[x])?fa[x]:x)); rotate(x); } upt(x);}inline void access(int x){ for(int y=0;x;y=x,x=fa[x]){ splay(x);tr[x][1]=y; if(y)fa[y]=x; }}inline int findroot(int x){ access(x);splay(x); while(pushrev(x),tr[x][0])x=tr[x][0]; splay(x); return x;}inline void makeroot(int x){ access(x);splay(x); rev[x]^=1;}inline void link(int x,int y){ makeroot(x);fa[x]=y;}inline void cut(int x,int y){ makeroot(x); access(y);splay(y); if(tr[x][0]||tr[x][1]||fa[x]!=y||tr[y][get(x)^1])return; tr[y][0]=0;fa[x]=0;}inline void split(int u,int v){ makeroot(u);access(v);splay(v);}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)key[i]=read(); for(int i=1;i<=m;i++){ int op=read(),u=read(),v=read(); if(op==0){ split(u,v); printf("%d\n",val[v]); } if(op==1){ if(findroot(u)!=findroot(v))link(u,v); } if(op==2){ if(findroot(u)==findroot(v))cut(u,v); } if(op==3){ access(u);splay(u); key[u]=v;upt(u); } } return 0;}