关键词：
干脆整个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 ",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 }
刷题洛谷p3690模板linkcuttree（动态树）(代码片段)
题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情
p3690模板linkcuttree（动态树）(代码片段)
P3690【模板】LinkCutTree（动态树）注意：不要把$fa[x]$和$nrt(x)$混在一起！#include<cstdio>voidswap(int&a,int&b)a^=b^=a^=b;#defineN300005intn,m,s[N],v[N],ch[2][N],fa[N],rev[N];#definelcch[0][x]#definercch[1][x]boolnrt(intx)returnch[0][fa[x]]==x||ch[1][fa[x]]==x;voidu... 查看详情
数据结构专题-学习笔记：linkcuttree动态树
1.前言LinkCutTree动态树，简称LCT，是一种维护动态森林的数据结构。前置知识：Splay。2.LCT例题：P3690【模板】动态树（LinkCutTree）2.1实链剖分实链剖分也是一种对树的剖分方式，类似于重链剖分和长链剖分，其将一棵树上的边，随... 查看详情
p3690模板linkcuttree（动态树）(代码片段)
LCTLCT即Link-Cut-Tree维护一个森林，支持很多操作，比如：维护链上信息（min，max，sum，xor。。。。。。）换根动态维护联通性维护子树信息概念虚边：连接儿子与父亲，儿子记录父亲，父亲不记录儿子（父不认子）实边：父子互... 查看详情
luogup3690模板linkcuttree（动态树）lct模板
P3690【模板】LinkCutTree（动态树）题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和... 查看详情
洛谷p3690模板linkcuttree（lct）(代码片段)
题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情
ac日记——模板linkcuttree洛谷p3690
【模板】LinkCutTree 思路： LCT模板； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn300005intn,m,val[maxn];inttop,ch[maxn][2],f[maxn],xr[maxn],q[maxn],rev[maxn];inlinevoidin(int&now 查看详情
linkcuttree学习笔记
从这里开始动态树问题和LinkCutTree一些定义access操作换根操作link和cut操作时间复杂度证明LinkCutTree维护链上信息LinkCutTree维护子树信息小结动态树问题和LinkCutTree 动态树问题是一类要求维护一个有根树森林，支持对树的分割,... 查看详情
linkcuttree动态树小结(代码片段)
动态树有些类似树链剖分+并查集的思想，是用splay维护的lct的根是动态的，"轻重链"也是动态的，所以并没有真正的轻重链动态树的操作核心是把你要把修改/询问/...等等一系列的操作的树链放到一个splay里，然后用splay根据相对... 查看详情
luogu3690模板linkcuttree（动态树）
参考there和there#include<iostream>#include<cstdio>usingnamespacestd;intn,m,val[300005],ch[300005][2],sum[300005],fa[300005],uu,vv,opt;intrev[300005];voidpushDown(intx)if(rev[x])swap(ch[x][0 查看详情
luogup3690模板linkcuttree（动态树）
#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<cstdlib>#include<climits>#include<stack>#include<vector>#include<queue& 查看详情
lct(linkcuttree)动态树(代码片段)
模板参考：https://blog.csdn.net/saramanda/article/details/55253627几个知识点：1、LCT中用Splay维护链，这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护，就是辅助树中每个节点左儿子的深度小于当前节点的深度... 查看详情
luogu3690模板linkcuttree（动态树）
题目luogu3690硫硼作者想提醒大家，WA了TLE了RE了的，也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情
模板linkcuttree（动态树）
题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的... 查看详情
luogup3690模板linkcuttree（动态树）[lct]
题目背景动态树题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证... 查看详情
[p3690]linkcuttree(代码片段)
Description:给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两个整数(x，y)，代... 查看详情
linkcuttree求最小生成树(代码片段)
对边建点，原图中的边转化为点的点-边的点-点的点于是用LCT维护连通关系，并支持查询最大值位置即可#include<bits/stdc++.h>usingnamespacestd;constintN=300005;intn,m,val[N],t1,t2,t3;namespacelct inttop,q[N],ch[N][2],fa[N],rev[N]; intmx[N]; inlin 查看详情
bzoj-3779重组病毒linkcuttree+线段树+dfs序
3779:重组病毒TimeLimit: 20Sec MemoryLimit: 512MBSubmit: 224 Solved: 95[Submit][Status][Discuss]Description黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和... 查看详情