Link Cut Tree
题目背景
动态树
题目描述
给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。
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。
输入输出格式
输入格式：
第1行两个整数，分别为n和m，代表点数和操作数。
第2行到第n+1行，每行一个整数，整数在［1，10^9］内，代表每个点的权值。
第n+2行到第n+m+1行，每行三个整数，分别代表操作类型和操作所需的量。
输出格式：
对于每一个0号操作，你须输出x到y的路径上点权的xor和。
输入输出样例
说明
数据范围： 1$ \leq $ N,M $ \leq $ 3 · $ 10^5 $
分析：
Link Cut Tree模板题。具体的知识点这位大佬已经讲的特别好了，推荐这位大佬的博客<http://www.cnblogs.com/flashhu/p/8324551.html>，蒟蒻就只放代码了。
Code：
//It is made by HolseLee on 27th June 2018
//Luogu.org P3690
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+;
int n,m,val[N];
struct LCT{
int fa[N],ch[N][],xr[N],sign[N],q[N],top;
inline void pushup(int u)
{
xr[u]=xr[ch[u][]]^xr[ch[u][]]^val[u];
}
inline void change(int u)
{
int temp=ch[u][];
ch[u][]=ch[u][];
ch[u][]=temp;
sign[u]^=;
}
inline void pushdown(int u)
{
if(!sign[u])return;
if(ch[u][])change(ch[u][]);
if(ch[u][])change(ch[u][]);
sign[u]=;
}
inline bool isroot(int u)
{
return (ch[fa[u]][]!=u&&ch[fa[u]][]!=u);
}
inline void rotate(int x)
{
int y=fa[x],z=fa[y];
int k=(ch[y][]==x);
int w=ch[x][k^];
if(!isroot(y))ch[z][ch[z][]==y]=x;
ch[x][k^]=y;ch[y][k]=w;
if(w)fa[w]=y;fa[y]=x;fa[x]=z;
pushup(y);pushup(x);
}
inline void splay(int x)
{
top=;q[top]=x;
for(int i=x;!isroot(i);i=fa[i])
q[++top]=fa[i];
while(top)pushdown(q[top--]);
while(!isroot(x)){
int y=fa[x],z=fa[y];
if(!isroot(y))
(ch[y][]==x)^(ch[z][]==y)?rotate(x):rotate(y);
rotate(x);
}
}
void access(int u)
{
for(int i=;u;i=u,u=fa[u]){
splay(u);ch[u][]=i;pushup(u);}
}
void makeroot(int u)
{
access(u);splay(u);change(u);
}
inline int find(int u)
{
access(u);splay(u);
while(ch[u][])pushdown(u),u=ch[u][];
//splay(u);
return u;
}
void split(int u,int v)
{
makeroot(u);access(v);splay(v);
}
void cut(int u,int v)
{
makeroot(u);
if(find(v)==u&&fa[u]==v&&!ch[u][]){
fa[u]=ch[v][]=;pushup(v);}
}
void link(int u,int v)
{
makeroot(u);
if(find(v)!=u)fa[u]=v;
}
}T;
inline int read()
{
char ch=getchar();int num=;bool flag=false;
while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}
while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}
return flag?-num:num;
}
int main()
{
n=read();m=read();int opt,x,y;
for(int i=;i<=n;i++){
val[i]=read();T.xr[i]=val[i];}
for(int i=;i<=m;i++){
opt=read();x=read();y=read();
if(opt==){
T.split(x,y);
printf("%d\n",T.xr[y]);}
else if(opt==){T.link(x,y);}
else if(opt==){T.cut(x,y);}
else if(opt==){
T.splay(x);val[x]=y;T.pushup(x);}
}
return ;
}