关键词：
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, val[300005], ch[300005][2], sum[300005], fa[300005], uu, vv, opt;
int rev[300005];
void pushDown(int x)
if(rev[x])
swap(ch[x][0], ch[x][1]);
rev[ch[x][0]] ^= 1;
rev[ch[x][1]] ^= 1;
rev[x] = 0;
bool isRoot(int x)
return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
void xf(int x)
if(!isRoot(x)) xf(fa[x]);
pushDown(x);
bool getW(int x)
return ch[fa[x]][1]==x;
void upd(int x)
sum[x] = sum[ch[x][0]] ^ sum[ch[x][1]] ^ val[x];
void rotate(int x)
int old=fa[x], oldf=fa[old], w=getW(x);
if(!isRoot(old)) ch[oldf][ch[oldf][1]==old] = x;
ch[old][w] = ch[x][w^1]; ch[x][w^1] = old;
fa[ch[x][w^1]] = x; fa[ch[old][w]] = old; fa[x] = oldf;
upd(old); upd(x);
void splay(int x)
xf(x);
while(!isRoot(x))
int f=fa[x];
if(!isRoot(f)) rotate(getW(x)==getW(f)?f:x);
rotate(x);
void access(int x)
int y=0;
while(x)
splay(x);
ch[x][1] = y;
upd(x);
y = x;
x = fa[x];
void makeRoot(int x)
access(x);
splay(x);
rev[x] ^= 1;
int query(int u, int v)
makeRoot(u);
access(v);
splay(v);
return sum[v];
int findRoot(int x)
access(x);
splay(x);
while(ch[x][0])
x = ch[x][0];
splay(x);//谜之降低常数
return x;
void link(int u, int v)
makeRoot(u);
fa[u] = v;
void cut(int u, int v)
makeRoot(u);
access(v);
splay(v);
if(ch[u][0] || ch[u][1] || fa[u]!=v || ch[v][getW(u)^1]) return ;
ch[v][0] = fa[u] = 0;
void change(int u, int v)
val[u] = v;
access(u);
splay(u);
int main()
cin>>n>>m;
for(int i=1; i<=n; i++)
scanf("%d", &val[i]);
while(m--)
scanf("%d %d %d", &opt, &uu, &vv);
if(opt==0) printf("%d\n", query(uu, vv));
else if(opt==1 && findRoot(uu)!=findRoot(vv))
link(uu, vv);
else if(opt==2 && findRoot(uu)==findRoot(vv))
cut(uu, vv);
else if(opt==3) change(uu, vv);
return 0;
luogup3690模板linkcuttree（动态树）
#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<cstdlib>#include<climits>#include<stack>#include<vector>#include<queue& 查看详情
luogup3690模板linkcuttree（动态树）lct模板
P3690【模板】LinkCutTree（动态树）题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和... 查看详情
luogup3690模板linkcuttree（动态树）[lct]
题目背景动态树题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证... 查看详情
洛谷3690：模板linkcuttree——题解(代码片段)
https://www.luogu.org/problemnew/show/P3690给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：... 查看详情
p3690linkcuttree(动态树)
干脆整个LCT模板吧。缺个链上修改和子树操作，链上修改的话join(u,v)然后把vsplay到树根再打个标记就好。至于子树操作...以后有空的话再学(咕咕咕警告)1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintN=1e5+10;5intn,m,a[N],X... 查看详情
p3690模板linkcuttree（动态树）(代码片段)
哇，做梦也没想到我居然能写LCT题意：给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通... 查看详情
刷题洛谷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... 查看详情
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 查看详情
洛谷p3690模板linkcuttree（lct）(代码片段)
题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情
p3690模板linkcuttree（动态树）(代码片段)
LCTLCT即Link-Cut-Tree维护一个森林，支持很多操作，比如：维护链上信息（min，max，sum，xor。。。。。。）换根动态维护联通性维护子树信息概念虚边：连接儿子与父亲，儿子记录父亲，父亲不记录儿子（父不认子）实边：父子互... 查看详情
数据结构专题-学习笔记：linkcuttree动态树
1.前言LinkCutTree动态树，简称LCT，是一种维护动态森林的数据结构。前置知识：Splay。2.LCT例题：P3690【模板】动态树（LinkCutTree）2.1实链剖分实链剖分也是一种对树的剖分方式，类似于重链剖分和长链剖分，其将一棵树上的边，随... 查看详情
模板linkcuttree（动态树）
题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的... 查看详情
[p3690]linkcuttree(代码片段)
Description:给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两个整数(x，y)，代... 查看详情
luogu3690(代码片段)
非常好的一篇博客写下之前自己被困住的几个点吧：1.access找的不是到真实的根的一条路径，而是到能找到的最上面的splay的根(makeroot同理)2.findroot找的是x所在原树的树根（深度最小），并旋转至当前一棵splay的根tips:具体的还是... 查看详情
lct(linkcuttree)动态树(代码片段)
模板参考：https://blog.csdn.net/saramanda/article/details/55253627几个知识点：1、LCT中用Splay维护链，这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护，就是辅助树中每个节点左儿子的深度小于当前节点的深度... 查看详情
linkcuttree学习笔记
从这里开始动态树问题和LinkCutTree一些定义access操作换根操作link和cut操作时间复杂度证明LinkCutTree维护链上信息LinkCutTree维护子树信息小结动态树问题和LinkCutTree 动态树问题是一类要求维护一个有根树森林，支持对树的分割,... 查看详情
linkcuttree动态树小结(代码片段)
动态树有些类似树链剖分+并查集的思想，是用splay维护的lct的根是动态的，"轻重链"也是动态的，所以并没有真正的轻重链动态树的操作核心是把你要把修改/询问/...等等一系列的操作的树链放到一个splay里，然后用splay根据相对... 查看详情