LCT模板 ｃｏｄｅ：
#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ const int maxn=3e5+500; int n,m; /*==================Define Area================*/ namespace LCT { struct Node { int ch[2],fa,rev,sum,w; }t[maxn]; #define ls(o) t[o].ch[0] #define rs(o) t[o].ch[1] #define pa(o) t[o].fa int Which(int o) {return t[pa(o)].ch[1]==o;} int IsRoot(int o) {return t[pa(o)].ch[0]!=o&&t[pa(o)].ch[1]!=o;} void Update(int o) {t[o].sum=t[ls(o)].sum^t[rs(o)].sum^t[o].w;} void RevNode(int o) {t[o].rev^=1;swap(ls(o),rs(o));} void Pushdown(int o) { if(!o) return ; if(!t[o].rev) return ; if(ls(o)) RevNode(ls(o)); if(rs(o)) RevNode(rs(o)); t[o].rev=0; } void TreePushdown(int o) {if(!IsRoot(o)) TreePushdown(pa(o));Pushdown(o);} void Rotate(int o) { int f=t[o].fa,ff=t[f].fa,c=Which(o); if(!IsRoot(f)) t[ff].ch[Which(f)]=o;t[o].fa=ff; t[f].ch[c]=t[o].ch[c^1];t[t[f].ch[c]].fa=f; t[o].ch[c^1]=f;t[f].fa=o; Update(f);Update(o); } void Splay(int o) { TreePushdown(o); for(;!IsRoot(o);Rotate(o)) { if(!IsRoot(pa(o))) Rotate(Which(pa(o))==Which(o)?pa(o):o); } } void Access(int o) {for(int y=0;o;y=o,o=pa(o)) Splay(o),rs(o)=y,Update(o);} void MakeRoot(int o) {Access(o);Splay(o);RevNode(o);} int FindRoot(int o) {Access(o);Splay(o);while(ls(o)) Pushdown(o),o=ls(o);return o;} // void Link(int x,int y) {MakeRoot(x);t[x].fa=y;} void Link(int x,int y) {MakeRoot(x);if(FindRoot(y)==x) return ;t[x].fa=y;} // void Cut(int x,int y) {MakeRoot(x);Access(y);Splay(y);t[x].fa=t[y].ch[0]=0;Update(y);} void Cut(int x,int y) {MakeRoot(x);Access(y);Splay(y);if(FindRoot(y)!=x||t[x].fa!=y||t[x].ch[1]) return ;t[x].fa=t[y].ch[0]=0;Update(y);} void Split(int x,int y) {MakeRoot(x);Access(y);Splay(y);} } using namespace LCT; int main() { read(n);read(m); for(int i=1;i<=n;i++) { read(t[i].w); } while(m--) { int opt,x,y; read(opt);read(x);read(y); if(opt==0) Split(x,y),printf("%d\n",t[y].sum); if(opt==1) Link(x,y); if(opt==2) Cut(x,y); if(opt==3) t[x].w=y,Splay(x); } return 0; }转载于:https://www.cnblogs.com/Apocrypha/p/9477844.html
相关资源：JAVA上百实例源码以及开源项目