关键词：
题目
硫硼作者想提醒大家，WA 了 TLE 了 RE 了的，也许只是主函数写错了
代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
#define pa T[x].fa
#define l T[x].ch[0]
#define r T[x].ch[1]
const int N=300005;
struct lct
{
struct node
{
int ch[2],fa,sum,rev,w;//sum记录以当前节点为根的辅助树的权值和
}T[N];
bool son(int x){return T[pa].ch[1]==x;}//判断是否为右儿子
bool isroot(int x){return T[pa].ch[0]!=x&&T[pa].ch[1]!=x;}//判断节点x是否为所处辅助树的根
//每个辅助树之间是有连接的，即儿子都认父亲，父亲只认重儿子，所以当其父亲左右儿子都不为自己时，当前节点为所处辅助树的根
void reverse(int x){T[x].rev^=1;swap(l,r);}//翻转
void update(int x){T[x].sum=T[l].sum^T[r].sum^T[x].w;}//异或
void pushdown_once(int x)//下传翻转标记
{
if(!T[x].rev) return;
if(l) reverse(l); if(r) reverse(r);
T[x].rev=0;
}
void pushdown(int x){if(!isroot(x)) pushdown(pa);pushdown_once(x);}//从上往下翻转
void lk(int x,int y,int f)
{
T[x].ch[f]=y;
T[y].fa=x;
}
void rotate(int x)
{
int y=T[x].fa,z=T[y].fa,f=son(x);
if(!isroot(y)) T[z].ch[son(y)]=x;T[x].fa=z;//如果是根，儿子认父亲，父亲不认儿子
T[y].ch[f]=T[x].ch[f^1];T[T[x].ch[f^1]].fa=y;
T[x].ch[f^1]=y;T[y].fa=x;
update(y);update(x);
}
void splay(int x)//将x转至根
{
pushdown(x);
while(!isroot(x))
{
if(!isroot(pa)) rotate(son(pa)==son(x)? pa:x);
rotate(x);
}
}
/***/
void access(int x){for(int y=0;x;y=x,x=pa) splay(x),r=y,update(x);}//将当前节点至根的路径修改为一条重链
void makeroot(int x){access(x);splay(x);reverse(x);}//将x换为原树的根
int findroot(int x)//查询节点x所在树的根
{
access(x);splay(x);
while(l) pushdown_once(x),x=l;return x;
}
void link(int x,int y){makeroot(x);T[x].fa=y;}//将x接在y下方(反着接也可以)
void cut(int x,int y)//断开x,y的连接
{
makeroot(x);access(y);splay(y);
T[x].fa=T[y].ch[0]=0;update(y);
}
void split(int x,int y){makeroot(x);access(y);splay(y);}
}st;
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&st.T[i].w);
for(int i=1;i<=m;i++)
{
int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
if(opt==0) st.split(x,y),printf("%d
",st.T[y].sum);
if(opt==1) if (st.findroot(x)!=st.findroot(y)) st.link(x,y);
if(opt==2) if (st.findroot(x)==st.findroot(y)) st.cut(x,y);
if(opt==3) st.T[x].w=y,st.splay(x);
}
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根据相对... 查看详情