链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3282
题面：
3282: Tree
Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 2845 Solved: 1424
[Submit][Status][Discuss]
Description
给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。
操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。
保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。
Input
第１行两个整数,分别为Ｎ和Ｍ,代表点数和操作数。
第２行到第Ｎ＋１行,每行一个整数,整数在［１,１０＾９］内,代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行,每行三个整数,分别代表操作类型和操作所需的量。
１＜＝Ｎ，Ｍ＜＝３０００００
Output
对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。
Sample Input
3 3
1
2
3
1 1 2
0 1 2
0 1 1
1
2
3
1 1 2
0 1 2
0 1 1
Sample Output
3
1
1
思路:
模板题，练下手
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int M = 3e5+;
const int inf = 0x3f3f3f3f;
int n,m,sz,rt,c[M][],fa[M],v[M],sum[M],st[M],top;
bool rev[M]; inline void up(int x){
int l = c[x][],r = c[x][];
sum[x] = sum[l] ^ sum[r] ^ v[x];
} inline void pushrev(int x){
int t = c[x][];
c[x][] = c[x][]; c[x][] = t;
rev[x] ^= ;
} inline void pushdown(int x){
if(rev[x]){
int l = c[x][],r = c[x][];
if(l) pushrev(l);
if(r) pushrev(r);
rev[x] = ;
}
} inline bool nroot(int x){ //判断一个点是否为一个splay的根
return c[fa[x]][]==x||c[fa[x]][] == x;
} inline void rotate(int x){
int y = fa[x],z = fa[y],k = c[y][] == x;
int w = c[x][!k];
if(nroot(y)) c[z][c[z][]==y]=x;
c[x][!k] = y; c[y][k] = w;
if(w) fa[w] = y; fa[y] = x; fa[x] = z;
up(y);
} inline void splay(int x){
int y = x,z = ;
st[++z] = y;
while(nroot(y)) st[++z] = y = fa[y];
while(z) pushdown(st[z--]);
while(nroot(x)){
y = fa[x];z = fa[y];
if(nroot(y))
rotate((c[y][]==x)^(c[z][]==y)?x:y);
rotate(x);
}
up(x);
} //打通根节点到指定节点的实链，使得一条中序遍历从根开始以指定点结束的splay出现
inline void access(int x){
for(int y = ;x;y = x,x = fa[x])
splay(x),c[x][]=y,up(x);
} inline void makeroot(int x){ //换根，让指定点成为原树的根
access(x); splay(x); pushrev(x);
} inline int findroot(int x){ //寻找x所在原树的树根
access(x); splay(x);
while(c[x][]) pushdown(x),x = c[x][];
splay(x);
return x;
} inline void split(int x,int y){ //拉出x-y的路径成为一个splay
makeroot(x); access(y); splay(y);
} inline void cut(int x,int y){ //断开边
makeroot(x);
if(findroot(y) == x&&fa[y] == x&&!c[y][]){
fa[y] = c[x][] = ;
up(x);
}
} inline void link(int x,int y){ //连接边
makeroot(x);
if(findroot(y)!=x) fa[x] = y;
} int main()
{
int n,m,x,y,op;
scanf("%d%d",&n,&m);
for(int i = ;i <= n;i ++) scanf("%d",&v[i]);
while(m--){
scanf("%d%d%d",&op,&x,&y);
if(op==) split(x,y),printf("%d\n",sum[y]);
else if(op == ) link(x,y);
else if(op == ) cut(x,y);
else if(op == ) splay(x),v[x] = y;
}
return ;
}