关键词：
https://www.luogu.org/problemnew/show/P3690
给定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。
模板题就不说什么了。
我们多维护一个节点的key值（权值）和val值（splay中子树的异或和），每次update即可。
对于3操作我们把该节点access然后splay，更新key之后update即可。
剩下就是LCT基本操作。
UPT：18.4.2更新：
数据被加强了，多了删掉一个不存在的边导致的bug。
所以对于cut函数要多处理一遍，具体的处理方法就是打通x和y，这样x作为重链末端没有儿子，x的爸爸为y，y只有x一个儿子。
凡是不符合的即为没有该边。
#include<algorithm> #include<iostream> #include<cstring> #include<cctype> #include<cstdio> #include<vector> #include<queue> #include<cmath> using namespace std; const int N=3e5+5; int n,m,r,fa[N],tr[N][2],rev[N],q[N],key[N],val[N]; inline int read() int X=0,w=0;char ch=0; while(!isdigit(ch))w|=ch==\'-\';ch=getchar(); while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; inline bool get(int x) return tr[fa[x]][1]==x; inline bool isroot(int x) if(!fa[x])return 1; return tr[fa[x]][0]!=x&&tr[fa[x]][1]!=x; inline void upt(int x) int ans=0; if(tr[x][0])ans^=val[tr[x][0]]; if(tr[x][1])ans^=val[tr[x][1]]; val[x]=key[x]^ans; inline void pushrev(int x) if(!rev[x])return; swap(tr[x][0],tr[x][1]); if(tr[x][0])rev[tr[x][0]]^=1; if(tr[x][1])rev[tr[x][1]]^=1; rev[x]=0; inline void rotate(int x) int y=fa[x],z=fa[y],which=get(x); if(z&&!isroot(y))tr[z][tr[z][1]==y]=x; tr[y][which]=tr[x][which^1];fa[tr[y][which]]=y; fa[y]=x;tr[x][which^1]=y;fa[x]=z; upt(y);upt(x); inline void splay(int x) q[r=0]=x; for(int y=x;!isroot(y);y=fa[y])q[++r]=fa[y]; for(int i=r;i>=0;i--)pushrev(q[i]); while(!isroot(x)) if(!isroot(fa[x])) rotate((get(x)==get(fa[x])?fa[x]:x)); rotate(x); upt(x); inline void access(int x) for(int y=0;x;y=x,x=fa[x]) splay(x);tr[x][1]=y; if(y)fa[y]=x; inline int findroot(int x) access(x);splay(x); while(pushrev(x),tr[x][0])x=tr[x][0]; splay(x); return x; inline void makeroot(int x) access(x);splay(x); rev[x]^=1; inline void link(int x,int y) makeroot(x);fa[x]=y; inline void cut(int x,int y) makeroot(x); access(y);splay(y); if(tr[x][0]||tr[x][1]||fa[x]!=y||tr[y][get(x)^1])return; tr[y][0]=0;fa[x]=0; inline void split(int u,int v) makeroot(u);access(v);splay(v); int main() n=read(),m=read(); for(int i=1;i<=n;i++)key[i]=read(); for(int i=1;i<=m;i++) int op=read(),u=read(),v=read(); if(op==0) split(u,v); printf("%d\\n",val[v]); if(op==1) if(findroot(u)!=findroot(v))link(u,v); if(op==2) if(findroot(u)==findroot(v))cut(u,v); if(op==3) access(u);splay(u); key[u]=v;upt(u); return 0;
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
洛谷p3690模板linkcuttree（lct）(代码片段)
题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情
刷题洛谷p3690模板linkcuttree（动态树）(代码片段)
题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情
luogu3690模板linkcuttree（动态树）
题目luogu3690硫硼作者想提醒大家，WA了TLE了RE了的，也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情
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& 查看详情
luogup3690模板linkcuttree（动态树）lct模板
P3690【模板】LinkCutTree（动态树）题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和... 查看详情
luogup3690模板linkcuttree（动态树）[lct]
题目背景动态树题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证... 查看详情
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（动态树）(代码片段)
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... 查看详情
p3690模板linkcuttree（动态树）(代码片段)
LCTLCT即Link-Cut-Tree维护一个森林，支持很多操作，比如：维护链上信息（min，max，sum，xor。。。。。。）换根动态维护联通性维护子树信息概念虚边：连接儿子与父亲，儿子记录父亲，父亲不记录儿子（父不认子）实边：父子互... 查看详情
[p3690]linkcuttree(代码片段)
Description:给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两个整数(x，y)，代... 查看详情
数据结构专题-学习笔记：linkcuttree动态树
1.前言LinkCutTree动态树，简称LCT，是一种维护动态森林的数据结构。前置知识：Splay。2.LCT例题：P3690【模板】动态树（LinkCutTree）2.1实链剖分实链剖分也是一种对树的剖分方式，类似于重链剖分和长链剖分，其将一棵树上的边，随... 查看详情
ac日记——[sdoi2010]大陆争霸洛谷p3690
[SDOI2010]大陆争霸 思路： dijkstra模板； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn3005#definelllonglong#definemaxm70002<<2#defineINF1e13structNodeType{llid,dis;booloperator 查看详情
洛谷4238：模板多项式求逆——题解(代码片段)
https://www.luogu.org/problemnew/show/P4238如题所示，对998244353取模。板子没啥好说的。讲解看这位大佬：http://blog.miskcoo.com/2015/05/polynomial-inverse#include<cstdio>#include<cctype>#include<cstring>#inclu 查看详情
洛谷p3376模板网络最大流题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problemnew/show/3376题目描述如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。输入输出格式输入格式：第一行... 查看详情
洛谷p3374模板树状数组1题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=3374题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某一个数加上x2.求出某区间每一个数的和输... 查看详情
洛谷p3387模板缩点题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=3387题目背景缩点+DP题目描述给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权... 查看详情