本文主要是介绍LCT动态树-基础模板（luogu P3690），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
学习来自
P3690 【模板】Link Cut Tree （动态树）
给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。
0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。
1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。
2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。
3：后接两个整数(x，y)，代表将点x上的权值变成y。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
#define ls ch[x][0]
#define rs ch[x][1]
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=3e5+5;
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
//il int Add(int &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(int &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int f[N],ch[N][2],v[N],s[N],st[N];
bool r[N];
il bool isroot(int x){//判断节点是否为一个Splay的根return ch[f[x]][0]==x || ch[f[x]][1]==x;
}
il void pushup(int x){//上传信息s[x]=s[ls]^s[rs]^v[x];
}
il void reverse(int x){//翻转swap(ls,rs),r[x]^=1;
}
il void pushdown(int x){//判断并释放懒标记if(r[x]){if(ls) reverse(ls);if(rs) reverse(rs);r[x]=0;}
}
il void rotate(int x){//一次旋转int y=f[x],z=f[y],k=(ch[y][1]==x),w=ch[x][!k];if(isroot(y)) ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=w;if(w) f[w]=y;f[y]=x,f[x]=z;pushup(y);
}
il void splay(int x){//所有操作的目标都是该Splay的根int y=x,z=0;st[++z]=y;while(isroot(y)) st[++z]=y=f[y];while(z) pushdown(st[z--]);while(isroot(x)){y=f[x],z=f[y];if(isroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);rotate(x);}pushup(x);
}il void access(int x){//访问for(int y=0;x;x=f[y=x]){splay(x),rs=y,pushup(x);}
}
il void makeroot(int x){//将x换成根access(x),splay(x);reverse(x);
}
il int findroot(int x){//找根（在真实的树中的）access(x),splay(x);while(ls) pushdown(x),x=ls;splay(x);return x;
}
il void split(int x,int y){提取路径 makeroot(x);access(y),splay(y);
}
il void link(int x,int y){//连边makeroot(x);if(findroot(y)!=x) f[x]=y;
}
il void cut(int x,int y){//断边makeroot(x);if(findroot(y)==x && f[y]==x && !ch[y][0]){f[y]=ch[x][1]=0;pushup(x);}
}
/*
//保证合法的情况下
il void link(int x,int y){makeroot(x),f[x]=y;
}
il void cut(int x,int y){split(x,y);f[x]=ch[y][0]=0;
}
*/
int n,m,type,x,y;
int main() {read(n),read(m);for(int i=1; i<=n; ++i) read(v[i]);while(m--) {read(type),read(x),read(y);switch(type) {case 0:split(x,y);printf("%d\n",s[y]);break;case 1:link(x,y);break;case 2:cut(x,y);break;case 3:splay(x);v[x]=y;//先把x转上去再修改，不然会影响Splay信息的正确性}}return 0;
}
这篇关于LCT动态树-基础模板（luogu P3690）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
