【模板】LCT

题目链接：传送门
题解：LCT模板题

//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ls t[x].ch[0]
#define rs t[x].ch[1]
#define pa t[x].fa
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=300010;
int n,m;
inline int in()
{
    char ch=getchar();
    int f=1,tmp=0;
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}
    return tmp*f;
}
namespace lct
{
    struct node{int ch[2],fa,rev,sum,w;}t[N];
    inline int gi(int x) {return t[pa].ch[1]==x;}
    inline int upd(int x) {t[x].sum=t[ls].sum^t[rs].sum^t[x].w;}
    inline void rever(int x) {t[x].rev^=1;swap(ls,rs);}
    inline void pushdown(int x)
    {
        if(t[x].rev)
        {
            if(ls) rever(ls);
            if(rs) rever(rs);
            t[x].rev=0;
        }
    }
    inline bool isr(int x) {return t[pa].ch[0]!=x&&t[pa].ch[1]!=x;}
    void Push(int x) {if(!isr(x)) Push(pa);pushdown(x);}

    inline void rot(int x)
    {
        int f=t[x].fa,g=t[f].fa,o=gi(x);
        if(!isr(f)) t[g].ch[gi(f)]=x;t[x].fa=g;
// if(!isr(f)) t[g].ch[gi(f)]=x,t[x].fa=g;
        t[f].ch[o]=t[x].ch[!o];t[t[x].ch[!o]].fa=f;
        t[x].ch[!o]=f;t[f].fa=x;
        upd(f),upd(x);
    }

    inline void splay(int x)
    {
        Push(x);
        for(;!isr(x);rot(x))
            if(!isr(pa)) rot(gi(pa)==gi(x)?pa:x); 
    }

    inline void access(int x) 
    {
        for(int y=0; x;y=x,x=pa) 
        splay(x),rs=y,upd(x);
    }
    inline void maker(int x)
    {
        access(x);
        splay(x);
        rever(x);
    }
    inline int findr(int x)
    {
        access(x); splay(x);
        while(ls) pushdown(x),x=ls;
        return x;
    }
    inline void link(int x,int y) 
    {

        maker(x); 
        t[x].fa=y;
    }
    inline void cut(int x,int y)
    {
        maker(x); access(y); splay(y);
        t[x].fa=t[y].ch[0]=0; upd(y);
    }
    inline void split(int x,int y)
    {
        maker(x);
        access(y);
        splay(y);
    }
}
int main()
{
    n=in(),m=in();
    for(int i=1;i<=n;i++) lct::t[i].w=in();
    for(int i=1;i<=m;i++)
    {
        int op=in(),x=in(),y=in();
        if(op==0) lct::split(x,y),printf("%d\n",lct::t[y].sum);
        if(op==1) if(lct::findr(x)!=lct::findr(y)) lct::link(x,y);
        if(op==2) if(lct::findr(x)==lct::findr(y)) lct::cut(x,y);
        if(op==3) lct::t[x].w=y,lct::splay(x);
    } 
    return 0;
}

PS：一个if语句后的分号写成逗号，调了一个小时