干脆整个LCT模板吧。
缺个链上修改和子树操作，链上修改的话join(u,v)然后把v splay到树根再打个标记就好。
至于子树操作...以后有空的话再学(咕咕咕警告)
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1e5+10; 5 int n,m,a[N],Xor[N],fa[N],ch[N][2],flp[N],sta[N],tp; 6 #define l(u) ch[u][0] 7 #define r(u) ch[u][1] 8 void rev(int u) {flp[u]^=1,swap(l(u),r(u));} 9 void pu(int u) {Xor[u]=Xor[l(u)]^a[u]^Xor[r(u)];} 10 void pd(int u) {if(flp[u])rev(l(u)),rev(r(u)),flp[u]=0;} 11 int sf(int u) {return u==r(fa[u]);} 12 bool isrt(int u) {return u!=l(fa[u])&&u!=r(fa[u]);} 13 void rot(int u) { 14 int v=fa[u],f=sf(u); 15 if(!isrt(v))ch[fa[v]][sf(v)]=u; 16 ch[v][f]=ch[u][f^1],fa[ch[v][f]]=v; 17 fa[u]=fa[v],ch[u][f^1]=v,fa[v]=u,pu(v); 18 } 19 void splay(int u) { 20 sta[tp=0]=u; 21 for(int v=u; !isrt(v); v=fa[v])sta[++tp]=fa[v]; 22 for(; ~tp; pd(sta[tp--])); 23 for(; !isrt(u); rot(u))if(!isrt(fa[u])&&sf(fa[u])==sf(u))rot(fa[u]); 24 pu(u); 25 } 26 void access(int u) {for(int v=0; u; splay(u),r(u)=v,pu(u),u=fa[v=u]);} 27 void makert(int u) {access(u),splay(u),rev(u);} 28 void join(int u,int v) {makert(u),access(v),splay(v);} 29 int findrt(int u) {access(u),splay(u); for(; l(u); pd(u),u=l(u)); splay(u); return u;} 30 void link(int u,int v) {makert(u); if(findrt(v)==u)return; fa[u]=v;} 31 void cut(int u,int v) {join(u,v); if(l(v)!=u||r(u))return; fa[u]=l(v)=0;} 32 void upd(int u,int x) {makert(u),a[u]=x;} 33 int qry(int u,int v) {join(u,v); return Xor[v];} 34 int main() { 35 scanf("%d%d",&n,&m); 36 for(int i=1; i<=n; ++i)scanf("%d",&a[i]); 37 while(m--) { 38 int f,x,y; 39 scanf("%d%d%d",&f,&x,&y); 40 if(f==0)printf("%d\n",qry(x,y)); 41 else if(f==1)link(x,y); 42 else if(f==2)cut(x,y); 43 else if(f==3)upd(x,y); 44 } 45 return 0; 46 }