算法思想

动态树算法用于解决一类树上问题，涉及树边的连接和断开，并借助splay实现高效维护树上路径信息。算法细节见YangZhe的论文

代码实现

P3690 【模板】动态树（LCT）

#include<bits/stdc++.h>

#define ll long long
#define il inline 

using namespace std;

int read(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}
    return x*f;
}

const int N=1e5+10;

struct Link_Cut_Tree{
    int f[N],ch[N][2],sum[N],val[N],rev[N],stk[N];
    il bool notroot(int x){
        return (ch[f[x]][0]==x)||(ch[f[x]][1]==x);
    }
    il void pushup(int x){
        sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^val[x];
    }
    il void pushrev(int x){
        swap(ch[x][0],ch[x][1]);
        rev[x]^=1;
    }
    il void pushdown(int x){
        if(rev[x]){
            if(ch[x][0]) pushrev(ch[x][0]);
            if(ch[x][1]) pushrev(ch[x][1]);
            rev[x]=0;
        }
    }
    il void rotate(int x){
        int y=f[x],z=f[y];
        int d=ch[y][1]==x,w=ch[x][d^1];
        if(notroot(y)) ch[z][ch[z][1]==y]=x;ch[x][d^1]=y;ch[y][d]=w;
        if(w) f[w]=y;f[y]=x;f[x]=z;
        pushup(y);pushup(x);
    }
    il void splay(int x){
        int u=x,top=0;
        while(notroot(u)) stk[++top]=u=f[u];
        while(top) pushdown(stk[top--]);
        while(notroot(x)){
            int y=f[x],z=f[y];
            if(notroot(y)) (ch[z][0]==y)^(ch[y][0]==x)?rotate(x):rotate(y);
            rotate(x);
        }
    }
    il void access(int x){
        for(int y=0;x;x=f[y=x]){
            splay(x);ch[x][1]=y;pushup(x);
        }
    }
    il void makeroot(int x){
        access(x);splay(x);pushrev(x);
    }
    il int findroot(int x){
        access(x);splay(x);
        while(ch[x][0]) pushdown(x),x=ch[x][0];
        splay(x);
        return x;

    }
    il void split(int x,int y){
        makeroot(x);access(y);splay(y);
    }
    il void link(int x,int y){
        makeroot(x);
        if(findroot(y)!=x) f[x]=y;
    }
    il void cut(int x,int y){
        makeroot(x);
        if(findroot(y)==x&&f[y]==x&&!ch[y][0]){
            f[y]=ch[x][1]=0;
            pushup(x);
        }
    }
} lct;

int n,m;

int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        int x=read();
        lct.val[i]=lct.sum[i]=x;
    }
    for(int i=1;i<=m;i++){
        int op=read(),x=read(),y=read();
        if(op==0){
            lct.split(x,y);
            printf("%d\n",lct.sum[y]);
        }
        if(op==1){
            lct.link(x,y);
        }
        if(op==2){
            lct.cut(x,y);
        }
        if(op==3){
            lct.splay(x);
            lct.sum[x]^=lct.val[x]^y;
            lct.val[x]=y;
        }
    }
    return 0;
}