LG3690 【【模板】Link Cut Tree （动态树）】

终于去写\(LCT\)了
板子
#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define maxn 300005

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

int n,m;

int fa[maxn],v[maxn],s[maxn],ch[maxn][2],st[maxn],rev[maxn];

inline int nroot(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}

inline void pushup(int x) {s[x]=s[ch[x][0]]^s[ch[x][1]]^v[x];}

inline void pushdown(int x) {

    if(!rev[x]) return;

    rev[x]=0,rev[ch[x][0]]^=1,rev[ch[x][1]]^=1;

    std::swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);

    std::swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);

}

inline void rotate(int x) {

    int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][k^1];

    if(nroot(y)) ch[z][ch[z][1]==y]=x;

    ch[x][k^1]=y,ch[y][k]=w;

    pushup(y),pushup(x);fa[w]=y;fa[y]=x,fa[x]=z;

}

inline void splay(int x) {

    int y=x,top=0;

    st[++top]=x;

    while(nroot(y)) st[++top]=fa[y],y=fa[y];

    while(top) pushdown(st[top--]);

    while(nroot(x)) {

        int y=fa[x];

        if(nroot(y)) rotate((ch[y][1]==x)^(ch[fa[y]][1]==y)?x:y);

        rotate(x);

    }

}

inline void access(int x) {

    for(re int y=0;x;y=x,x=fa[x])

        splay(x),ch[x][1]=y,pushup(x);

}

inline void makeroot(int x) {

    access(x);splay(x);rev[x]^=1;std::swap(ch[x][0],ch[x][1]);

}

inline int findroot(int x) {

    access(x);splay(x);

    while(ch[x][0]) pushdown(x),x=ch[x][0];

    splay(x);return x;

}

inline void split(int x,int y) {

    makeroot(x);access(y);splay(y);

}

inline void link(int x,int y) {

    makeroot(x);

    if(findroot(y)!=x)fa[x]=y;

}

inline void cut(int x,int y) {

    makeroot(x);

    if(findroot(y)==x&&fa[y]==x&&!ch[y][0]) ch[x][0]=fa[y]=0,pushup(x);

}

int main()

{

    n=read(),m=read();

    for(re int i=1;i<=n;i++) v[i]=read();

    int opt,x,y;

    while(m--) {

        opt=read(),x=read(),y=read();

        if(opt==0) split(x,y),printf("%d\n",s[y]);

        if(opt==1) link(x,y);

        if(opt==2) cut(x,y);

        if(opt==3) splay(x),v[x]=y,pushup(x);

    }

    return 0;

}
巴特西

LG3690 【【模板】Link Cut Tree （动态树）】

最新文章

热门文章
