BZOJ 3282 Tree link cut trees

Description

給定Ｎ個點以及每個點的權值，要你處理接下來的Ｍ個操作。操作有４種。操作從０到３編号。點從１到Ｎ編号。

０：後接兩個整數（ｘ，ｙ），代表詢問從ｘ到ｙ的路徑上的點的權值的ｘｏｒ和。保證ｘ到ｙ是聯通的。

１：後接兩個整數（ｘ，ｙ），代表連接配接ｘ到ｙ，若ｘ到Ｙ已經聯通則無需連接配接。

２：後接兩個整數（ｘ，ｙ），代表删除邊（ｘ，ｙ），不保證邊（ｘ，ｙ）存在。

３：後接兩個整數（ｘ，ｙ），代表将點Ｘ上的權值變成Ｙ。

Input

第１行兩個整數，分别為Ｎ和Ｍ，代表點數和操作數。

第２行到第Ｎ＋１行，每行一個整數，整數在［１，１０＾９］内，代表每個點的權值。

第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三個整數，分别代表操作類型和操作所需的量。

Output

對于每一個０号操作，你須輸出Ｘ到Ｙ的路徑上點權的Ｘｏｒ和。

Sample Input

3 3

1

2

3

1 1 2

0 1 2

0 1 1

Sample Output

3

1

HINT

１＜＝Ｎ，Ｍ＜＝３０００００

​​傳送門​​

竟然找到水題了……

結果洛谷上有這題，竟然貼了個很老舊的……于是大緻整改了一下。

#include<bits/stdc++.h>
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*10+ch-'0';ch=getchar();}
    return x*f;
}
const int 
    N=300005;
int n,m;
struct LCT{
    int val,xsum,pre,son[2];
    bool rev;
}tree[N];
bool isroot(int x){
    return tree[tree[x].pre].son[0]!=x &&
           tree[tree[x].pre].son[1]!=x;
}
void up(int x){
    if (x){
        tree[x].xsum=tree[x].val;
        if (tree[x].son[0]) tree[x].xsum^=tree[tree[x].son[0]].xsum;
        if (tree[x].son[1]) tree[x].xsum^=tree[tree[x].son[1]].xsum;
    }
}
void down(int x){
    if (x && tree[x].rev){
        swap(tree[x].son[0],tree[x].son[1]);
        tree[tree[x].son[0]].rev^=1;
        tree[tree[x].son[1]].rev^=1;
        tree[x].rev^=1;
    }
}
void Rotate(int x){  
    int y=tree[x].pre,z=tree[y].pre,l,r;  
    if (tree[y].son[0]==x) l=0; else l=1;  
    r=l^1;  
    if (!isroot(y))  
        if (tree[z].son[0]==y) tree[z].son[0]=x;  
            else tree[z].son[1]=x;  
    tree[x].pre=z,tree[y].pre=x;  
    tree[y].son[l]=tree[x].son[r];  
    tree[tree[x].son[r]].pre=y;  
    tree[x].son[r]=y;  
    up(y);  
}  
int stk[N];  
void splay(int x){  
    int top=1;stk[1]=x;  
    for (int i=x;!isroot(i);i=tree[i].pre)  
        stk[++top]=tree[i].pre;  
    while (top) down(stk[top--]);  
    while (!isroot(x)){  
        int y=tree[x].pre,z=tree[y].pre;  
        if (!isroot(y))  
            if (tree[y].son[0]==x^tree[z].son[0]==y) Rotate(x);  
                else Rotate(y);  
        Rotate(x);  
    }  
    up(x);  
}  
void access(int x){
    for (int t=0;x;t=x,x=tree[x].pre)
        splay(x),tree[x].son[1]=t,up(x);
}
void makeroot(int x){
    access(x),splay(x);
    tree[x].rev^=1;
}
int findroot(int x){
    access(x),splay(x);
    while (tree[x].son[0]) x=tree[x].son[0];
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y),splay(y); 
}
void cut(int x,int y){
    split(x,y);
    tree[y].son[0]=tree[x].pre=0;
}
void link(int x,int y){
    makeroot(x);
    tree[x].pre=y;
}
int main(){
    n=read(),m=read();
    for (int i=1;i<=n;i++) tree[i].val=tree[i].xsum=read();
    int opt,x,y;
    while (m--){
        opt=read(),x=read(),y=read();
        if (!opt){
            split(x,y);
            printf("%d\n",tree[y].xsum);
        }
        if (opt==1 && findroot(x)!=findroot(y)) link(x,y);
        if (opt==2 && findroot(x)==findroot(y)) cut(x,y);
        if (opt==3){
            access(x),splay(x);
            tree[x].val=y;
            up(x);
        }
    }
    return 0;
}