关键词：
坑了好久，本来打算就这样弃着，最近又被神秘力量驱使来学这个东西，过程很痛苦但最终还是知道它到底是啥了
它可以用来对森林进行各种操作，为了快速地实现各种操作，我们要像树剖一样把整个森林剖成许多条链，每条链都用splay维护
为了在splay中体现链中节点的相对顺序，splay以节点深度为关键字（从小到大）
不同链之间的连接通过splay根节点的父亲来体现
如图中所示，假设链$a$的splay根节点为$p$，链$b$中的节点$x$与链$a$相连，那么我们让$fa_p=x$
把森林剖成这些链之后，我们需要对其进行各种操作，比如形态改变和路径信息查询
所有的操作都基于一个东西：access
access($x$)，就是“访问”节点$x$
感性地理解，一般访问树中的节点都要从树根开始走，所以这个操作实际上就是把$x$到根路径上的点都弄到一棵splay里
实现不难，我们需要从$x$按照链一直往上跳，遇到非链的边就把它连到$x$所属的链上，并把涉及到的其他链适当断开
具体点，给一个真代码
void access(int x){
int y=0;
while(x){
splay(x);
ch[x][1]=y;
pushup(x);
y=x;
x=fa[x];
}
}
代码中的$y$表示当前链往下一条链的splay根节点，当执行splay($x$)后，$x$以及$x$的左子树都是$x$往上同一条链的点（因为深度$\leq dep_x$），把它连上之前的链（深度$\geq dep_x$），然后往上跳，一直到树根就ok了
如何判断一个点$u$是否为一棵splay的根？当$lson_{fa_u}\neq u$且$rson_{fa_u}\neq u$时，说明$u$是一棵splay的根节点（因为根节点的父亲指向另一条链的节点）
这样我们就完成了lct中的核心操作access，接下来用这个access随意乱搞就可以实现各种功能了
1.makeroot($x$)：钦点$x$为树的根
void makert(int x){
access(x);
splay(x);
reverse(x);
}
假设原来的根为$r$，因为原来深度从小到大是$r\rightarrow x$，现在变为$x\rightarrow r$，所以深度的相对大小反了，所以需要把整棵splay区间翻转
2.link($x$,$y$)：连接一条边$(x,y)$
void link(int x,int y){
makeroot(x);
fa[x]=y;
}
3.cut($x$,$y$)：删除边$(x,y)$
void cut(int x,int y){
makeroot(x);
access(y);
splay(y);
fa[x]=0;
ch[y][0]=0;
pushup(y);
}
makeroot($x$)并access($y$)之后，这棵splay中就只有$x$和$y$两个节点了，断开就好
4.operate($x$,$y$)：对$x\rightarrow y$这条路径做一些操作（询问，修改等）
void cut(int x,int y){
makeroot(x);
access(y);
splay(y);
//...
}
makeroot($x$)并access($y$)之后，这棵splay中只有$x\rightarrow y$路径上的点，我们可以对这棵splay做任何平衡树能做的操作
5.connected($x$,$y$)：判断$x$和$y$是否在同一棵树中
bool connected(int x,int y){
if(x==y)return 1;
makeroot(x);
access(y);
splay(y);
return fa[x]!=0;
}
如果$x$和$y$在同一棵树上，那么在makeroot($x$)并access($y$)之后，$x$和$y$就在同一棵splay上了，再splay($y$)，$x$就会被挤下去，即是说$fa_x\ne0$
刚接触的时候会觉得很不可理解，但认真去画一画，调一调就知道它的含义是啥了
数据结构专题-学习笔记：linkcuttree动态树
1.前言LinkCutTree动态树，简称LCT，是一种维护动态森林的数据结构。前置知识：Splay。2.LCT例题：P3690【模板】动态树（LinkCutTree）2.1实链剖分实链剖分也是一种对树的剖分方式，类似于重链剖分和长链剖分，其将一棵树上的边，随... 查看详情
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 查看详情
p3690linkcuttree(动态树)
干脆整个LCT模板吧。缺个链上修改和子树操作，链上修改的话join(u,v)然后把vsplay到树根再打个标记就好。至于子树操作...以后有空的话再学(咕咕咕警告)1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintN=1e5+10;5intn,m,a[N],X... 查看详情
[]linkcuttree
坑了好久，本来打算就这样弃着，最近又被神秘力量驱使来学这个东西，过程很痛苦但最终还是知道它到底是啥了它可以用来对森林进行各种操作，为了快速地实现各种操作，我们要像树剖一样把整个森林剖成许多条链，每条链... 查看详情
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& 查看详情
linkcuttree（无图慎入）(代码片段)
类似树链剖分（其实直接记住就可以了），提前放代码1#include<cstdio>2#include<cstdlib>3#include<iostream>4#include<algorithm>5#include<cstring>6#include<climits>7#include<cmath>8#define 查看详情
luogu3690模板linkcuttree（动态树）
题目luogu3690硫硼作者想提醒大家，WA了TLE了RE了的，也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情
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 查看详情
ural题目1553.cavesandtunnels（linkcuttree改动点权，求两点之间最大）
1553.CavesandTunnelsTimelimit:3.0secondMemorylimit:64MBAfterlandingonMarssurface,scientistsfoundastrangesystemofcavesconnectedbytunnels.Sotheybegantoresearchitusingremotecontrolledrobots.Itwasfoundout 查看详情
bzoj-2555substring后缀自动机+linkcuttree
2555:SubStringTimeLimit: 30Sec MemoryLimit: 512MBSubmit: 1936 Solved: 551[Submit][Status][Discuss]Description 懒得写背景了，给你一个字符串init，要求你支持两 查看详情
模板linkcuttree（动态树）
题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的... 查看详情
lct(linkcuttree)动态树(代码片段)
模板参考：https://blog.csdn.net/saramanda/article/details/55253627几个知识点：1、LCT中用Splay维护链，这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护，就是辅助树中每个节点左儿子的深度小于当前节点的深度... 查看详情
linkcuttree动态树小结(代码片段)
动态树有些类似树链剖分+并查集的思想，是用splay维护的lct的根是动态的，"轻重链"也是动态的，所以并没有真正的轻重链动态树的操作核心是把你要把修改/询问/...等等一系列的操作的树链放到一个splay里，然后用splay根据相对... 查看详情
luogup3690模板linkcuttree（动态树）lct模板
P3690【模板】LinkCutTree（动态树）题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和... 查看详情
bzoj-3779重组病毒linkcuttree+线段树+dfs序
3779:重组病毒TimeLimit: 20Sec MemoryLimit: 512MBSubmit: 224 Solved: 95[Submit][Status][Discuss]Description黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和... 查看详情
linkcuttree
//知识点:LCT/*By:Luckyblock*/#include<cstdio>#include<ctype.h>#include<algorithm>#definels(t[x].son[0])#definers(t[x].son[1])constintkMaxn=1e5+10;//=============================================================structLink_Cut_Tree_Nodeintson[2],fa;intxr,rev;t[kMaxn];intn,m,val[kMa... 查看详情
洛谷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：... 查看详情