Description
给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。
操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。
保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。
Input
第１行两个整数,分别为Ｎ和Ｍ,代表点数和操作数。
第２行到第Ｎ＋１行,每行一个整数,整数在［１,１０＾９］内,代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行,每行三个整数,分别代表操作类型和操作所需的量。
１＜＝Ｎ，Ｍ＜＝３０００００
Output
对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。
Sample Input
3 3 1 2 3 1 1 2 0 1 2 0 1 1
Sample Output
3 1
解题思路：
这是LCT很好的模板。
主要难点是处理一下路径权值，和判断两个点是否联通（以防重边）
路径权值：单独将x到y的路径提取（split）Splay维护链的时候在将节点处权值上传，最后查值就好
判断有无x到y的边：将x到y的路径提取，若直接连接无中间值就是有边。
代码：
1 #include2 #include 3 #include 4 #define lll tr[spc].ch[0] 5 #define rrr tr[spc].ch[1] 6 #define ls ch[0] 7 #define rs ch[1] 8 const int N=200000; 9 struct trnt{ 10 int ch[2]; 11 int lzt; 12 int fa; 13 int val; 14 int sum; 15 bool anc; 16 }tr[N]; 17 int n,m; 18 int cnt; 19 bool whc(int spc) 20 { 21 return tr[tr[spc].fa].rs==spc; 22 } 23 void pushup(int spc) 24 { 25 tr[spc].sum=tr[lll].sum^tr[rrr].sum^tr[spc].val; 26 return ; 27 } 28 void trr(int spc) 29 { 30 if(!spc) 31 return ; 32 std::swap(lll,rrr); 33 tr[spc].lzt^=1; 34 return ; 35 } 36 void pushdown(int spc) 37 { 38 if(tr[spc].lzt) 39 { 40 trr(lll); 41 trr(rrr); 42 tr[spc].lzt=0; 43 } 44 return ; 45 } 46 void recal(int spc) 47 { 48 if(!tr[spc].anc) 49 recal(tr[spc].fa); 50 pushdown(spc); 51 } 52 void rotate(int spc) 53 { 54 int f=tr[spc].fa; 55 bool k=whc(spc); 56 tr[f].ch[k]=tr[spc].ch[!k]; 57 tr[spc].ch[!k]=f; 58 if(tr[f].anc) 59 { 60 tr[f].anc=false; 61 tr[spc].anc=true; 62 }else 63 tr[tr[f].fa].ch[whc(f)]=spc; 64 tr[spc].fa=tr[f].fa; 65 tr[f].fa=spc; 66 tr[tr[f].ch[k]].fa=f; 67 pushup(f); 68 pushup(spc); 69 } 70 void splay(int spc) 71 { 72 recal(spc); 73 while(!tr[spc].anc) 74 { 75 int ft=tr[spc].fa; 76 if(tr[ft].anc) 77 { 78 rotate(spc); 79 return ; 80 } 81 if(whc(spc)^whc(ft)) 82 rotate(spc); 83 else 84 rotate(ft); 85 rotate(spc); 86 } 87 return ; 88 } 89 void access(int spc) 90 { 91 int lsts=0; 92 while(spc) 93 { 94 splay(spc); 95 tr[rrr].anc=true; 96 tr[lsts].anc=false; 97 rrr=lsts; 98 pushup(spc); 99 lsts=spc;100 spc=tr[spc].fa;101 }102 return ;103 }104 void Mtr(int spc)105 {106 107 access(spc);108 splay(spc);109 trr(spc);110 return ;111 }112 int spmrt(int spc)113 {114 access(spc);115 splay(spc);116 while(lll)117 {118 pushdown(spc);119 spc=lll;120 }121 return spc;122 }123 void split(int x,int y)124 {125 Mtr(x);126 access(y);127 splay(y);128 }129 void Link(int x,int y)130 {131 Mtr(x);132 if(spmrt(y)!=x)133 tr[x].fa=y;134 return ;135 }136 void Cut(int x,int y)137 {138 Mtr(x);139 if(spmrt(y)==x&&tr[x].fa==y&&!tr[y].rs)140 {141 tr[x].anc=1;142 tr[y].ls=0;143 tr[x].fa=0;144 pushup(y);145 }146 return ;147 }148 int main()149 {150 scanf("%d%d",&n,&m);151 for(int i=1;i<=n;i++)152 {153 scanf("%d",&tr[i].val);154 tr[i].anc=true;155 }156 while(m--)157 {158 int cmd,x,y;159 scanf("%d%d%d",&cmd,&x,&y);160 if(cmd==0)161 {162 split(x,y);163 printf("%d\n",tr[y].sum);164 }165 if(cmd==1)166 Link(x,y);167 if(cmd==2)168 Cut(x,y);169 if(cmd==3)170 {171 splay(x);172 tr[x].val=y;173 pushup(x);174 }175 }176 return 0;177 }