关键词：
类似树链剖分（其实直接记住就可以了），提前放代码
1 #include<cstdio> 2 #include<cstdlib> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstring> 6 #include<climits> 7 #include<cmath> 8 #define N (int)(3e5+5) 9 using namespace std; 10 11 int n,m,st[N],z; 12 struct tree 13 14 int vi,si,son[2],rev,fa; 15 #define vi(x) t[x].vi 16 #define si(x) t[x].si 17 #define fa(x) t[x].fa 18 #define rev(x) t[x].rev 19 #define son(x,y) t[x].son[y] 20 t[N]; 21 22 void pushup(int x) si(x)=vi(x)^si(son(x,0))^si(son(x,1)); 23 void pushr(int x) swap(son(x,0),son(x,1));rev(x)^=1; 24 void pushdown(int x) 25 26 if(rev(x)) 27 28 if(son(x,0)) pushr(son(x,0)); 29 if(son(x,1)) pushr(son(x,1)); 30 rev(x)=0; 31 32 33 34 int get(int x) return son(fa(x),1)==x; 35 bool nroot(int x) return son(fa(x),0)==x||son(fa(x),1)==x; 36 37 void rotate(int x) 38 39 int y=fa(x),z=fa(y),k=get(x); 40 if(nroot(y)) son(z,get(y))=x;fa(x)=z; 41 son(y,k)=son(x,k^1);if(son(y,k)) fa(son(y,k))=y; 42 son(x,k^1)=y;fa(y)=x;pushup(y);pushup(x); 43 44 void Splay(int x) 45 46 int y=x;st[++(z=0)]=y; 47 while(nroot(y)) st[++z]=y=fa(y); 48 while(z) pushdown(st[z--]); 49 while(nroot(x)) 50 51 int y=fa(x),z=fa(y); 52 if(nroot(y)) rotate(get(x)==get(y)?y:x); 53 rotate(x); 54 55 pushup(x); 56 57 58 void access(int x) 59 60 for(int y=0;x;x=fa(y=x)) 61 Splay(x),son(x,1)=y,pushup(x); 62 63 void makeroot(int x) 64 65 access(x);Splay(x); 66 pushr(x);pushup(x); 67 68 void split(int x,int y) makeroot(x);access(y);Splay(y); 69 int findroot(int x) 70 71 access(x);Splay(x); 72 while(son(x,0)) pushdown(x),x=son(x,0); 73 return x; 74 75 76 bool link(int x,int y) 77 78 makeroot(x); 79 if(findroot(y)==x) return false; 80 fa(x)=y;return true; 81 82 83 bool cut(int x,int y) 84 85 makeroot(x); 86 if(findroot(y)!=x||fa(x)!=y||son(x,1)) return 1; 87 fa(x)=son(y,0)=0;pushup(y); 88 89 90 int main() 91 92 scanf("%d%d",&n,&m); 93 for(int i=1;i<=n;i++) scanf("%d",&vi(i)); 94 for(int i=1,type,x,y;i<=m;i++) 95 96 scanf("%d%d%d",&type,&x,&y); 97 switch(type) 98 99 case 0:split(x,y);printf("%d ",si(y));break; 100 case 1:link(x,y);break; 101 case 2:cut(x,y);break; 102 case 3:Splay(x);vi(x)=y; 103 104 105 return 0; 106
Link Cut Tree的一些注意：
同一个Splay中没有相同深度点
Splay需要先放标记
然后Splay的根的父亲不一定是0
认父不认子，就是儿子父亲不变，但是父亲只记录一个儿子
核心操作：
access 提取一个到根的路径
考虑现在是一个由多个Splay组成的树（或者森林），首先肯定是将x转到根节点，然后直接换到这个Splay的整个父亲（就是Splay中深度最小的点的父亲），然后因为需要将整个Splay和父亲相连，为了维护性质，需要将它父亲的其他儿子断掉，直接Splay（父亲），然后将右边儿子改为这个Splay（注意这个是一个递推的过程）
makeroot 将这个点变为整个树的根
比较简单，主要首先就是开辟一条到根的路径，然后Splay，但是依旧不是深度最小的点，直接打入翻转标记即可
然后。。。其他就通过这些直接推就可以了（其实就是比较懒）
lct(linkcuttree)动态树(代码片段)
模板参考：https://blog.csdn.net/saramanda/article/details/55253627几个知识点：1、LCT中用Splay维护链，这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护，就是辅助树中每个节点左儿子的深度小于当前节点的深度... 查看详情
linkcuttree动态树小结(代码片段)
动态树有些类似树链剖分+并查集的思想，是用splay维护的lct的根是动态的，"轻重链"也是动态的，所以并没有真正的轻重链动态树的操作核心是把你要把修改/询问/...等等一系列的操作的树链放到一个splay里，然后用splay根据相对... 查看详情
洛谷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：... 查看详情
p3690模板linkcuttree（动态树）(代码片段)
哇，做梦也没想到我居然能写LCT题意：给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通... 查看详情
洛谷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：后接两... 查看详情
二叉搜索树的实现源码（源码较长，请慎入）(代码片段)
实现二叉搜索树的一种好方法是利用二叉树抽象数据类型。我们以BisTree这个名称来代表二叉搜索树这种数据结构。通过typedef方式将BisTree(二叉搜索树)实现为BiTree（二叉树）的别名。采用typedef方法使得二叉搜索树具有了某种程度... 查看详情
[模板]linkcuttree(代码片段)
...：后接两个整数(x，y)，代表将点x上的权值变成y。Solution(LinkCutTree)模板题(findroot)后要(Splay)到根？不然复杂度不保证？？？在洛谷上实测(535ms)，还算比较快吧函数变量名奇异+神仙缩行(ightarrow)还是别看了Code?//2019.1.2618:41-22:54#inclu... 查看详情
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... 查看详情
[wc2006]水管局长-linkcuttree(代码片段)
...,t1,t2,t3,t4;structEdgeintu,v,w,f;e[N];structOperatinginto,p,q;op[N];structLinkCutTreeinttop,q[N],ch[N][2],fa[N],rev[N],mx[N],mp[N],val[N];inlinevoidpushup(intx)mx[0]=mp[0]=0;mx[x]=max(max(mx[ch[x][0]],mx[ch[x][1]]),val[x]);if(mx[x]==mx[ch[x][0]])mp[x]=mp[ch[x][0]];if(mx[x]==mx[ch[x][1]])mp[x]=mp[ch... 查看详情
如果程序员面试时大家都说真话…画面过于真实，易引起不适请慎入(代码片段)
????????关注后回复 “进群” ，拉你进程序员交流群????????面试官：你好，这是你面试的第一家公司吗？程序员小王：当然不是啦，面了30多家，都不要我。面试官：哦哦哦，没事，我们面试... 查看详情
[p3690]linkcuttree(代码片段)
Description:给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两个整数(x，y)，代... 查看详情
dedecms列表页有图调用缩略图无图留空的方法(代码片段)
...则不显示任何图片。其实也就是去掉默认织梦的“暂无图片”的小图， 查看详情
p3690模板linkcuttree（动态树）(代码片段)
LCTLCT即Link-Cut-Tree维护一个森林，支持很多操作，比如：维护链上信息（min，max，sum，xor。。。。。。）换根动态维护联通性维护子树信息概念虚边：连接儿子与父亲，儿子记录父亲，父亲不记录儿子（父不认子）实边：父子互... 查看详情
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 动态树问题是一类要求维护一个有根树森林，支持对树的分割,... 查看详情
tcp/ip,udp,icmp,arp协议族简介－－纯图慎点
ISO/OSI的网络模型架构 TCP/IP参考模型的层次结果 以太网头部结构 以太网属于数据链路层，属于最基本的协议结构 IP协议 IP协议为TCP，UDP，ICMP提供最基本的数据传输通路 ICMP协议 IC... 查看详情
luogu3690模板linkcuttree（动态树）
题目luogu3690硫硼作者想提醒大家，WA了TLE了RE了的，也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情