Link-Cut tree（动态树）良心讲解

我会带着你远行 2023-06-04 07:59 27阅读 0赞

先放板子，以后慢慢填坑

/*
    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。
    */
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=3e6+7;
    int fa[maxn],lazy[maxn];
    int sum[maxn],val[maxn];
    int sta[maxn];
    int son[maxn][2];
    bool not_root(int x){
        return son[fa[x]][1]==x||son[fa[x]][0]==x;
    }
    void pushup(int x){
        sum[x]=sum[son[x][1]]^sum[son[x][0]]^val[x];
    }
    void reverse(int x){
        swap(son[x][1],son[x][0]);
        lazy[x]^=1;
    }
    void Josh_Dun(int x){
        if(!lazy[x]) return;
        if(son[x][0]) reverse(son[x][0]);
        if(son[x][1]) reverse(son[x][1]);    
        lazy[x]=0;    
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],k=son[y][1]==x,v=son[x][!k];
        if(not_root(y)) son[z][son[z][1]==y]=x;
        son[x][!k]=y;son[y][k]=v;
        if(v) fa[v]=y;
        fa[y]=x,fa[x]=z;
        pushup(y);
        pushup(x);
    }
    void splay(int x){
        int y=x,top=0;sta[++top]=y;
        while(not_root(y)){
             sta[++top]=y=fa[y];
        }
        while(top) Josh_Dun(sta[top--]);
        while(not_root(x)){
            y=fa[x],top=fa[y];
            if(not_root(y)) rotate((son[y][0]==x)^(son[top][0]==y)?x:y);
            rotate(x);
        }
        pushup(y); 
        pushup(x);
    }
    void access(int x){
        for(int y=0;x;x=fa[y=x]){
            splay(x);
            son[x][1]=y;
            pushup(x);
        }
    }
    void makeroot(int x){
        access(x);splay(x);reverse(x);
    }
    int findroot(int x){
        access(x);splay(x);
        while(son[x][0]){Josh_Dun(x);x=son[x][0];} 
        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) fa[x]=y;
    }
    void cut(int x,int y){
        split(x,y);
        if(findroot(y)==x&&fa[x]==y&&!son[x][1]){
            fa[x]=son[y][0]=0;
            pushup(y);
        }
    }
    int n,m,opt,x,y;
    int main(){
        scanf("%d%d",&n,&m);
        for(register int i=1;i<=n;i++){
            scanf("%d",&val[i]);
        }
        for(register int i=1;i<=m;i++){
            scanf("%d%d%d",&opt,&x,&y);
            if(opt==0) split(x,y),printf("%d\n",sum[y]);
            else if(opt==1) link(x,y);
            else if(opt==2) cut(x,y);
            else splay(x),val[x]=y;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11246555.html