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
解题思路：
这是LCT很好的模板。
主要难点是处理一下路径权值，和判断两个点是否联通（以防重边）
路径权值：单独将x到y的路径提取（split）Splay维护链的时候在将节点处权值上传，最后查值就好
判断有无x到y的边：将x到y的路径提取，若直接连接无中间值就是有边。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll tr[spc].ch[0]
#define rrr tr[spc].ch[1]
#define ls ch[0]
#define rs ch[1]
const int N=;
struct trnt{
int ch[];
int lzt;
int fa;
int val;
int sum;
bool anc;
}tr[N];
int n,m;
int cnt;
bool whc(int spc)
{
return tr[tr[spc].fa].rs==spc;
}
void pushup(int spc)
{
tr[spc].sum=tr[lll].sum^tr[rrr].sum^tr[spc].val;
return ;
}
void trr(int spc)
{
if(!spc)
return ;
std::swap(lll,rrr);
tr[spc].lzt^=;
return ;
}
void pushdown(int spc)
{
if(tr[spc].lzt)
{
trr(lll);
trr(rrr);
tr[spc].lzt=;
}
return ;
}
void recal(int spc)
{
if(!tr[spc].anc)
recal(tr[spc].fa);
pushdown(spc);
}
void rotate(int spc)
{
int f=tr[spc].fa;
bool k=whc(spc);
tr[f].ch[k]=tr[spc].ch[!k];
tr[spc].ch[!k]=f;
if(tr[f].anc)
{
tr[f].anc=false;
tr[spc].anc=true;
}else
tr[tr[f].fa].ch[whc(f)]=spc;
tr[spc].fa=tr[f].fa;
tr[f].fa=spc;
tr[tr[f].ch[k]].fa=f;
pushup(f);
pushup(spc);
}
void splay(int spc)
{
recal(spc);
while(!tr[spc].anc)
{
int ft=tr[spc].fa;
if(tr[ft].anc)
{
rotate(spc);
return ;
}
if(whc(spc)^whc(ft))
rotate(spc);
else
rotate(ft);
rotate(spc);
}
return ;
}
void access(int spc)
{
int lsts=;
while(spc)
{
splay(spc);
tr[rrr].anc=true;
tr[lsts].anc=false;
rrr=lsts;
pushup(spc);
lsts=spc;
spc=tr[spc].fa;
}
return ;
}
void Mtr(int spc)
{ access(spc);
splay(spc);
trr(spc);
return ;
}
int spmrt(int spc)
{
access(spc);
splay(spc);
while(lll)
{
pushdown(spc);
spc=lll;
}
return spc;
}
void split(int x,int y)
{
Mtr(x);
access(y);
splay(y);
}
void Link(int x,int y)
{
Mtr(x);
if(spmrt(y)!=x)
tr[x].fa=y;
return ;
}
void Cut(int x,int y)
{
Mtr(x);
if(spmrt(y)==x&&tr[x].fa==y&&!tr[y].rs)
{
tr[x].anc=;
tr[y].ls=;
tr[x].fa=;
pushup(y);
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&tr[i].val);
tr[i].anc=true;
}
while(m--)
{
int cmd,x,y;
scanf("%d%d%d",&cmd,&x,&y);
if(cmd==)
{
split(x,y);
printf("%d\n",tr[y].sum);
}
if(cmd==)
Link(x,y);
if(cmd==)
Cut(x,y);
if(cmd==)
{
splay(x);
tr[x].val=y;
pushup(x);
}
}
return ;
}