关键词：
模板参考：https://blog.csdn.net/saramanda/article/details/55253627
几个知识点：
1、LCT中用Splay维护链，这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护，就是辅助树中每个节点左儿子的深度小于当前节点的深度，当前节点的深度小于右儿子的深度。
2、LCT相当于多棵splay被虚线连在一起，即splay森林；而最开始的时候是N个单独的点与他的父亲用虚线相连，每个点是一棵splay。
3、无论树怎样旋转，怎样变换，读入时所连接(link)的边（没有被cut的），一直都连着的
4、在每棵splay中每一个结点左子树中的节点都是他在原树中的祖先，右子树中的结点都是他在原树中的孩子。
5、splay森林实例：
原树：
一种可能的splay森林：
6、access(x)操作：
—————————题目—————————
1、Cave 洞穴勘测 HYSBZ - 2049
题意：一开始有n个洞穴，两两之间没有通道。每次将两个洞穴连接或者两个洞穴之间的通道摧毁，或者询问两个洞穴之间能否连通。
思路：LCT模板题。连接则通过link(u,v)实现，摧毁通过cut(u,v)实现，两个洞穴能否连通则考虑u的根和v的根是否相同。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int maxn = 10000 + 10; 5 struct LCT 6 7 struct node 8 9 int fa, ch[2]; //父亲(Splay对应的链向上由轻边连着哪个节点)、左右儿子 10 int reverse;//区间反转标记 11 bool is_root; //是否是所在Splay的根 12 //int siz; 13 //int val; 14 //int sum; 15 Tree[maxn]; 16 int n; 17 //int v[maxn];//每个结点的值 18 void init() 19 20 for (int i = 1; i <= n; i++) 21 22 Tree[i].reverse = Tree[i].fa = Tree[i].ch[0] = Tree[i].ch[1] = 0; 23 Tree[i].is_root = true; 24 //Tree[i].siz = 1; 25 //Tree[i].val = Tree[i].sum = v[i]; 26 27 28 29 bool getson(int x) 30 //x是否为重儿子 31 return x == Tree[Tree[x].fa].ch[1]; 32 33 bool isroot(int x) 34 35 return Tree[Tree[x].fa].ch[0] != x && Tree[Tree[x].fa].ch[1] != x; 36 37 void pushreverse(int x) 38 39 if (!x)return; 40 swap(Tree[x].ch[0], Tree[x].ch[1]); 41 Tree[x].reverse ^= 1; 42 43 void pushdown(int x) 44 //下传反转标记 45 if (Tree[x].reverse) 46 47 pushreverse(Tree[x].ch[0]); 48 pushreverse(Tree[x].ch[1]); 49 Tree[x].reverse = 0; 50 51 52 /* 53 void update(int x) 54 55 int l = Tree[x].ch[0], r = Tree[x].ch[1]; 56 Tree[x].siz = Tree[l].siz + Tree[r].siz + 1; 57 Tree[x].sum = Tree[l].sum + Tree[r].sum + Tree[x].val; 58 59 */ 60 void rotate(int x) 61 //将x旋转为根 62 if (Tree[x].is_root)return; 63 int k = getson(x), fa = Tree[x].fa; 64 int fafa = Tree[fa].fa; 65 pushdown(fa); pushdown(x); //先要下传标记 66 Tree[fa].ch[k] = Tree[x].ch[k ^ 1]; 67 if (Tree[x].ch[k ^ 1])Tree[Tree[x].ch[k ^ 1]].fa = fa; 68 Tree[x].ch[k ^ 1] = fa; 69 Tree[fa].fa = x; 70 Tree[x].fa = fafa; 71 if (!Tree[fa].is_root)Tree[fafa].ch[fa == Tree[fafa].ch[1]] = x; 72 else Tree[x].is_root = true, Tree[fa].is_root = false; 73 //update(fa);update(x); //如果维护了信息，就要更新节点 74 75 void push(int x) 76 77 if (!Tree[x].is_root) push(Tree[x].fa); 78 pushdown(x); 79 80 int getFa(int x) 81 //寻找x在原树的父亲 82 access(x); 83 Splay(x); 84 while (Tree[x].ch[0]) x = Tree[x].ch[0]; 85 return x; 86 87 void Splay(int x) 88 //让x成为Splay的根 89 push(x); //在Splay到根之前，必须先传完反转标记 90 for (int fa; !Tree[x].is_root; rotate(x)) 91 if (!Tree[fa = Tree[x].fa].is_root) 92 rotate((getson(x) == getson(fa)) ? fa : x); 93 94 95 96 void access(int x) 97 //访问某节点。作用是：对于访问的节点x，打通一条从树根（真实的LCT树）到x的重链；如果x往下是重链，那么把x往下的重边改成轻边。 98 int y = 0; 99 do 100 Splay(x); 101 Tree[Tree[x].ch[1]].is_root = true; 102 Tree[Tree[x].ch[1] = y].is_root = false; 103 //update(x); //如果维护了信息记得更新。 104 x = Tree[y = x].fa; 105 while (x); 106 107 void mroot(int x) 108 //把某个节点变成树根（这里的根指的是整棵LCT的根） 109 access(x);//使x与根结点处在同一棵splay中 110 Splay(x);//x成为这棵splay的根,x只有左儿子 111 pushreverse(x); 112 113 void link(int u, int v) 114 //连接u所在的LCT和v所在的LCT 115 mroot(u);//先让u成为其所在LCT的根 116 Tree[u].fa = v; 117 118 void cut(int u, int v) 119 //分离出两棵LCT 120 mroot(u); //先让u成为其所在LCT的根 121 access(v); //让u和v在同一棵Splay中 122 Splay(v); //连接u、v，u是v的左儿子 123 pushdown(v); //先下传标记 124 Tree[Tree[v].ch[0]].fa = Tree[v].fa; 125 Tree[Tree[v].ch[0]].is_root = true; 126 Tree[v].fa = 0; 127 Tree[v].ch[0] = 0; 128 //v的左孩子表示v上方相连的重链 129 //update(v); //记得维护信息 130 131 bool judge(int u, int v) 132 //判断u和v是否连通 133 while (Tree[u].fa) u = Tree[u].fa; 134 while (Tree[v].fa) v = Tree[v].fa; 135 return u == v; 136 137 lct; 138 int main() 139 140 int m; 141 while (~scanf("%d%d", &lct.n, &m)) 142 143 lct.init(); 144 char op[50]; 145 int u, v; 146 for (int i = 1; i <= m; i++) 147 148 scanf("%s%d%d", op, &u, &v); 149 if (op[0] == ‘Q‘) 150 151 if (lct.judge(u, v)) printf("Yes "); 152 else printf("No "); 153 154 else if (op[0] == ‘C‘) 155 156 lct.link(u, v); 157 158 else 159 160 lct.cut(u, v); 161 162 163 164 return 0; 165
2、Bounce 弹飞绵羊 HYSBZ - 2002
题意：有n个弹射装置，当绵羊在第i个弹射装置时，会被弹射到第i+val[i]个弹射装置，val数组记录每个弹射装置的弹射系数。有两个操作，要么询问当绵羊站在第x个弹射装置时会经过多少次被弹飞，要么修改某个弹射装置的系数。
思路：可以将第i个弹射装置与第i+val[i]个装置相连，新增第n+1个点作为树根，表示被弹飞。询问次数时即询问当前x到树根的距离即深度，然后-1即可（第n+1个结点不弹射）；修改某个弹射装置的系数相当于修改某个结点的父亲，先将原父亲删除，再重新连接父亲。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 const int maxn = 200000 + 10; 6 int val[maxn]; 7 struct LCT 8 9 struct node 10 11 int fa, ch[2]; //父亲(Splay对应的链向上由轻边连着哪个节点)、左右儿子 12 int reverse;//区间反转标记 13 bool is_root; //是否是所在Splay的根 14 int siz; 15 Tree[maxn]; 16 int n; 17 void init(int maxn) 18 19 for (int i = 1; i <= maxn; i++) 20 21 Tree[i].reverse = Tree[i].fa = Tree[i].ch[0] = Tree[i].ch[1] = 0; 22 Tree[i].is_root = true; 23 Tree[i].siz = 1; 24 25 26 27 bool getson(int x) 28 //x是否为重儿子 29 return x == Tree[Tree[x].fa].ch[1]; 30 31 bool isroot(int x) 32 33 return Tree[Tree[x].fa].ch[0] != x && Tree[Tree[x].fa].ch[1] != x; 34 35 void pushreverse(int x) 36 37 if (!x)return; 38 swap(Tree[x].ch[0], Tree[x].ch[1]); 39 Tree[x].reverse ^= 1; 40 41 void pushdown(int x) 42 //下传反转标记 43 if (Tree[x].reverse) 44 45 pushreverse(Tree[x].ch[0]); 46 pushreverse(Tree[x].ch[1]); 47 Tree[x].reverse = 0; 48 49 50 51 void update(int x) 52 53 int l = Tree[x].ch[0], r = Tree[x].ch[1]; 54 Tree[x].siz = 1; 55 if (l) Tree[x].siz += Tree[l].siz; 56 if (r) Tree[x].siz += Tree[r].siz; 57 58 59 void rotate(int x) 60 //将x旋转为根 61 if (Tree[x].is_root)return; 62 int k = getson(x), fa = Tree[x].fa; 63 int fafa = Tree[fa].fa; 64 pushdown(fa); pushdown(x); //先要下传标记 65 Tree[fa].ch[k] = Tree[x].ch[k ^ 1]; 66 if (Tree[x].ch[k ^ 1])Tree[Tree[x].ch[k ^ 1]].fa = fa; 67 Tree[x].ch[k ^ 1] = fa; 68 Tree[fa].fa = x; 69 Tree[x].fa = fafa; 70 if (!Tree[fa].is_root)Tree[fafa].ch[fa == Tree[fafa].ch[1]] = x; 71 else Tree[x].is_root = true, Tree[fa].is_root = false; 72 update(fa);update(x); //如果维护了信息，就要更新节点 73 74 void push(int x) 75 76 if (!Tree[x].is_root) push(Tree[x].fa); 77 pushdown(x); 78 79 int getFa(int x) 80 //寻找x在原树的父亲 81 access(x); 82 Splay(x); 83 while (Tree[x].ch[0]) x = Tree[x].ch[0]; 84 return x; 85 86 void Splay(int x) 87 //让x成为Splay的根 88 push(x); //在Splay到根之前，必须先传完反转标记 89 for (int fa; !Tree[x].is_root; rotate(x)) 90 if (!Tree[fa = Tree[x].fa].is_root) 91 rotate((getson(x) == getson(fa)) ? fa : x); 92 93 94 95 void access(int x) 96 //访问某节点。作用是：对于访问的节点x，打通一条从树根（真实的LCT树）到x的重链；如果x往下是重链，那么把x往下的重边改成轻边。 97 int y = 0; 98 do 99 Splay(x); 100 Tree[Tree[x].ch[1]].is_root = true; 101 Tree[Tree[x].ch[1] = y].is_root = false; 102 update(x); //如果维护了信息记得更新。 103 x = Tree[y = x].fa; 104 while (x); 105 106 void mroot(int x) 107 //把某个节点变成树根（这里的根指的是整棵LCT的根） 108 access(x);//使x与根结点处在同一棵splay中 109 Splay(x);//x成为这棵splay的根,x只有左儿子 110 pushreverse(x); 111 112 void link(int u, int v) 113 //连接u所在的LCT和v所在的LCT 114 mroot(u);//先让u成为其所在LCT的根 115 Tree[u].fa = v; 116 Tree[u].is_root = true; 117 118 void cut(int u, int v) 119 //分离出两棵LCT 120 mroot(u); //先让u成为其所在LCT的根 121 access(v); //让u和v在同一棵Splay中 122 Splay(v); //连接u、v，u是v的左儿子 123 pushdown(v); //先下传标记 124 Tree[Tree[v].ch[0]].fa = Tree[v].fa; 125 Tree[Tree[v].ch[0]].is_root = true; 126 Tree[v].fa = 0; 127 Tree[v].ch[0] = 0; 128 //v的左孩子表示v上方相连的重链 129 update(v); //记得维护信息 130 131 bool judge(int u, int v) 132 //判断u和v是否连通 133 while (Tree[u].fa) u = Tree[u].fa; 134 while (Tree[v].fa) v = Tree[v].fa; 135 return u == v; 136 137 int Query_deep(int x) 138 //询问x到LCT根的距离(深度) 139 access(x); 140 Splay(x); 141 return Tree[x].siz; 142 143 lct; 144 int main() 145 146 int m; 147 while (~scanf("%d", &lct.n)) 148 149 lct.init(lct.n+1);////让n+1表示被弹飞 150 for (int i = 1; i <= lct.n; i++) 151 152 scanf("%d", &val[i]); 153 int id = min(i + val[i], lct.n + 1); 154 lct.link(i, id); 155 156 lct.mroot(lct.n + 1); 157 scanf("%d", &m); 158 for (int i = 1; i <= m; i++) 159 160 int op, x; 161 scanf("%d%d", &op, &x); 162 x++; 163 if (op == 1) printf("%d ", lct.Query_deep(x)-1); 164 else 165 166 int v; 167 scanf("%d", &v); 168 int oid = min(x + val[x], lct.n + 1); 169 int nid = min(x + v, lct.n + 1); 170 lct.cut(x, oid); 171 lct.link(x, nid); 172 lct.mroot(lct.n + 1); 173 val[x] = v; 174 175 176 177 return 0; 178
luogup3690模板linkcuttree（动态树）lct模板
P3690【模板】LinkCutTree（动态树）题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和... 查看详情
luogup3690模板linkcuttree（动态树）[lct]
题目背景动态树题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证... 查看详情
数据结构专题-学习笔记：linkcuttree动态树
1.前言LinkCutTree动态树，简称LCT，是一种维护动态森林的数据结构。前置知识：Splay。2.LCT例题：P3690【模板】动态树（LinkCutTree）2.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：后接两... 查看详情
linkcuttree学习笔记
从这里开始动态树问题和LinkCutTree一些定义access操作换根操作link和cut操作时间复杂度证明LinkCutTree维护链上信息LinkCutTree维护子树信息小结动态树问题和LinkCutTree 动态树问题是一类要求维护一个有根树森林，支持对树的分割,... 查看详情
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 查看详情
p3690linkcuttree(动态树)
干脆整个LCT模板吧。缺个链上修改和子树操作，链上修改的话join(u,v)然后把vsplay到树根再打个标记就好。至于子树操作...以后有空的话再学(咕咕咕警告)1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintN=1e5+10;5intn,m,a[N],X... 查看详情
刷题洛谷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... 查看详情
lct(代码片段)
(LinkCutTree)（动态树）用实链剖分来实现，维护的对象为一个森林，将原树剖分为若干个辅助树，辅助树用(Splay)来维护辅助树内部用实边连接，辅助树之间用虚边连接，虚边总是由一棵(Splay)指向另一棵(Splay)的根，即为其中序遍... 查看详情
luogu3690模板linkcuttree（动态树）
题目luogu3690硫硼作者想提醒大家，WA了TLE了RE了的，也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情
link-cut-tree动态树算法(代码片段)
Link-Cut-Tree动态树算法总结动态树是一类要求维护森林连通性的算法总称，其中最常用的就是lct(Link-Cut-Tree).lct支持一下操作链上求和 链上求最值链上修改（前三项均可用树链剖分+线段树实现）断开树上的一条边连... 查看详情
动态树学习(代码片段)
学习动态树，我们首先需要了解到什么是Splay，推荐这一篇大聚聚yyb的博客。 我们在LCT中列写的Splay会以yyb的splay为基础作出改变，也是方便大家的后继学习，这样的排版。 LCT主要解决什么问题呢？维护一个数据结构... 查看详情
p3690模板linkcuttree（动态树）(代码片段)
LCTLCT即Link-Cut-Tree维护一个森林，支持很多操作，比如：维护链上信息（min，max，sum，xor。。。。。。）换根动态维护联通性维护子树信息概念虚边：连接儿子与父亲，儿子记录父亲，父亲不记录儿子（父不认子）实边：父子互... 查看详情
[模板]动态树/lct(代码片段)
简介LCT是一种数据结构,可以维护树的动态加边,删边,维护链上信息(满足结合律),单次操作时间复杂度(O(logn)).(不会证)思想类似树链剖分,因为splay可以换根,用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& 查看详情