类比树剖，树剖是通过静态地把一棵树剖成若干条链然后用一种支持区间操作的数据结构维护（比如线段树、树状数组），而LCT是动态地去处理这个问题。
大家都知道树剖用线段树维护，而LCT用维护。实际上同一条重链上的所有点才会被放在一棵中，而我们需要同时处理这若干条重链对应的若干棵之间的关系。因为一条重链上的每个点的深度互异，所以以深度为关键字。
我们规定一棵的根的为这条重链链顶节点在原树中的父亲节点。（前面的那个指的是中的）
而显然认了这个父亲之后，父亲不会认这个儿子：很简单，这两个点不在同一条重链上，所以父亲的左右儿子一定没有它。由此可以写一个判断一个点是不是根节点（当前的根节点）的函数：
bool isroot(int x){
return ch[0][fa[x]]!=x&&ch[1][fa[x]]!=x;
}
先讲LCT最重要的一个操作：，表示把节点到所在树（连通块）的根节点之间的路径全部变成重路径。
void access(int x){
for (int y=0;x;y=x,x=fa[x])
splay(x),ch[1][x]=y,pushup(x);
}
相当于是说要把这些在路径上的点全部搞到一棵里面去。
从下往上做，每次把splay到当前的根后，这个就会处于一个很微妙的位置：它的右儿子应该会接上这条重链下面的一部分，因为这条重链下面一部分的深度显然会大于。而所谓“下面的一部分”就是我们上一个处理的，这也就是为什么y=x,x=fa[x]了。
最开始的的下面不应该接上任何东西，所以的初值赋为0。
再就是另一个基本操作：,表示把节点设为所在树（连通块）的根节点。
我们先把access了，即连接了与根节点，然后再把splay到根，那么显然这个肯定会是中的最后一个元素（因为它深度最大），所以我们在这里打一个标记（区间翻转操作）即可。
void makeroot(int x){
access(x);splay(x);reverse(x);
}
剩下的操作就很简单了。
，找到节点所在树（连通块）的根节点。用这个操作可以维护连通性。
找到最左边（深度最小）的那个节点。
请注意暴跳了之后要把splay一下。你可能会问为什么我以前这样写没有被卡，那就请移步[Luogu4230]连环病原体
int findroot(int x){
access(x);splay(x);
while (ch[0][x]) x=ch[0][x];
splay(x);
return x;
}
，抠出到的路径，抠完以后是的根。
void split(int x,int y){
makeroot(x);access(y);splay(y);
}
，砍断到的边。
x的父亲和y的左儿子置0。
（split之后这一棵中就只剩和两个点了，所以才可以这么搞）
void cut(int x,int y){
split(x,y);fa[x]=ch[0][y]=0;
}
，连接到的边。
void link(int x,int y){
makeroot(x);fa[x]=y;
}
注意：
split请务必保证两个点联通
cut请务必保证两个点直接相连
link请务必保证两个点不联通
不然出现玄学错误谁都救不了你了
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 300005;
int n,m,opt,a,b,fa[N],ch[2][N],sum[N],val[N],rev[N],Stack[N],top;
int gi()
bool son(int x)
{
return x==ch[1][fa[x]];
}
bool isroot(int x)
{
return ch[0][fa[x]]!=x&&ch[1][fa[x]]!=x;
}
void pushup(int x)
{
sum[x]=sum[ch[0][x]]^sum[ch[1][x]]^val[x];
}
void reverse(int x)
void pushdown(int x)
void rotate(int x)
void splay(int x)
void access(int x)
{
for (int y=0;x;y=x,x=fa[x])
splay(x),ch[1][x]=y,pushup(x);
}
void makeroot(int x)
{
access(x);splay(x);reverse(x);
}
int findroot(int x)
{
access(x);splay(x);
while (ch[0][x]) x=ch[0][x];
splay(x);return x;
}
void split(int x,int y)
{
makeroot(x);access(y);splay(y);
}
void cut(int x,int y)
{
split(x,y);fa[x]=ch[0][y]=0;
}
void link(int x,int y)
{
makeroot(x);fa[x]=y;
}
int main()
return 0;
}
LCT还可以维护子树和，但仅限于维护而不支持修改
一般而言就是用一个数组维护每个节点的所有虚子树信息之和。
所以虚子树+实子树+自己=整个子树
那么在所有可能导致虚儿子关系变化的地方都要更新
其实仅有的不同只有三个函数：
放一下代码
void pushup(int x)
{
sum[x]=sum[ch[0][x]]+sum[ch[1][x]]+val[x]+sz[x];
}
void access(int x)
{
for (int y=0;x;y=x,x=fa[x])
splay(x),sz[x]+=sum[ch[1][x]]-sum[y],ch[1][x]=y,pushup(x);
}
void link(int x,int y)
{
makeroot(x);makeroot(y);fa[x]=y;sz[y]+=sum[x];pushup(y);
}
具体可参考BJOI2014大融合，cogs2701动态树
