【乱来】动态树 LCT（Link Cut Tree）
【乱来】动态树 LCT（Link Cut Tree）
Fenki_lo
·
2025-05-10 08:45:30
·
算法·理论
啊啊啊啊啊不会。膜拜9队。
前置知识：Splay平衡树
基本
在静态问题的背景上，对于树上问题，我们可以对其进行树剖并用线段树维护。但是对于会有分割/链接等动态操作的树，我们就要用到另一个动态的数据结构——LCT动态树。
LCT的实现会基于splay，这是因为splay能实现几乎所有线段树能实现的东西，而且非常方便。
LCT一般处理一些动态森林问题。
引入例题
P3690 【模板】动态树（LCT）
给定 n 个节点，每个节点有一个点权 a_i，现在给定 m 次操作，每次操作为以下四种其中之一：
0 x y 查询 x 到 y 路径上的点权异或和。
1 x y 连边 x,y。若 x,y 直接或间接连通则不需要连边。
2 x y 删去边 (x,y)。不保证这条边存在。
3 x y 将节点 x 的点权改为 y。
1\le n\le 10^5,1\le m\le3\times10^5,1\le a_i\le10^9
过程
不难判断出这是动态森林问题，一开始的每一个点都算一棵树。
首先我们要知道LCT的具体分割链的方式：实链剖分。
有以下定义：
偏爱儿子：类似于重儿子，父亲与偏爱儿子在原树上处于同一条链，注意：偏爱儿子是任意选择的一个儿子，这种任意性使得它能应用splay。
实边：连接父亲与偏爱儿子的边。
虚边：实边以外的边。
实链：由实边及其连接的节点构成的链。
这些概念我们记住就好，因为它们只是方便我们理解LCT上的操作映射的原树上是怎样的，在代码中并不会体现到。
接下来我们需要一些辅助树来分别管理原森林中的每一棵树。
辅助树关键性质
辅助树由一些splay构成，每一棵splay都对应原树上的一条实链，并且按照深度浅的在左侧，深度深的在右侧来组织。 即中序遍历一棵splay后我们可以获得一条从上到下顺序的实链。
原树中每一个节点与辅助树中节点分别对应。
辅助树中每一棵splay的根的父亲节点为原树上其对应的实链的链顶节点的父亲节点。注意，这类在辅助树上的父亲节点只有儿子连向父亲，但父亲不连儿子，对应原树上一条虚边。
由于辅助树以上性质，在代码中我们实际上只需改动辅助树即可，不需要改动原树。（前文说过
以下是一棵原树到辅助树的转换例子。
辅助树可能不是唯一的。
考虑原树与辅助树的结构关系（oi-wiki神力）
原树中的实链：实链的节点都在辅助树的一棵splay中。
原树中的虚链：辅助树中splay的根指向的父亲节点左右儿子都不指向这个根节点。
注意：原树中的根不等于辅助树的根。
辅助树中的splay可以在满足辅助树与splay性质下任意换根（转换）。
虚实链变换可以在辅助树上轻松完成，因此这样就可以实现动态维护实链分割。
变量定义
下面的所有变量都是在辅助树上节点的关联变量。
---
### 宏定义
```cpp
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
```
接下来是对各类函数的详细分析。
## 类线段树操作
## pushdown(x)
下放翻转标记。
```cpp
void pushdown(ll x){
if(tag[x]) rev(ls(x)),rev(rs(x)),tag[x]=0;
}
```
## pushup(x)
更新路径异或和。在另外的一些题目中，可能需要维护路径权值和之类的东西。
```cpp
void pushup(ll x){
sum[x]=sum[ls(x)]^sum[rs(x)]^a[x];
}
```
## splay操作
## get(x)
判断 $x$ 是 $f_x$ 的右儿子还是左儿子 $(0/1)$。
```cpp
bool get(ll x){
return rs(f[x])==x;
}
```
## rotate(x)
rotate就是splay中的旋转操作，很基本。但这里要注意，splay的根节点指向的父亲本来应该是空的，但放在辅助树中，它可能会通过虚边指向一个父亲，然而这个父亲的任意儿子都不能指向它，因此需要特判。
```cpp
void rotate(ll x){
ll y=f[x],z=f[y];
ll k=get(x);
if(!isroot(y)) ch[z][get(y)]=x;//特判
ch[y][k]=ch[x][k^1],f[ch[x][k^1]]=y;
ch[x][k^1]=y,f[y]=x,f[x]=z;
pushup(y),pushup(x);
}
```
## splay(x)
将节点 $x$ 旋转至**其所处splay的根部**。还是splay板子操作，在翻转前需要更新当前splay先。
当然默认是转到这棵splay的根部，也可以自己加参数转到别的点位，这要看题目需要。
void splay(ll x){
update(x);
while(!isroot(x)){
ll y=f[x];
if(!isroot(y)) rotate(get(x)==get(y) ? y : x);
rotate(x);
}
}
isroot及update函数会在下面讲到。
LCT 操作
isroot(x)
判断 x 是否为其所处splay的根。根据辅助树性质，当 f_x 任一儿子都不指向 x 时 x 就是当前splay的根。
bool isroot(ll x){
return (ls(f[x])!=x)&&(rs(f[x])!=x);
}
update(x)
从上往下更新 x 所处splay的根到 x 的路径，递归处理即可。
void update(ll x){
if(!isroot(x)) update(f[x]);
pushdown(x);
return ;
}
rev(x)
当前节点需要反转两边的儿子时进行的处理。（变换节点深度关系）
void rev(ll x){
swap(ls(x),rs(x)),tag[x]^=1;
}
access(x)
这步操作是LCT中最重要的操作之一。
其目的为将 x 所在原树上的根到 x 的路径变为一条实链，于是在辅助树上操作使得其映射到原树上后达到这一目的。
void access(ll x){//重点
for(int y=0;x;x=f[y=x]) splay(x),rs(x)=y,pushup(x);
}
下面举一个例子讲解一下。
如图，access(11) 在原树树上代表着：
将11到根节点的路径上所有节点和边变为偏爱儿子和实边。
将11到根节点这条路径上的所有节点的儿子和对应的边除了位于路径上的节点与边外全部变为轻儿子和虚边。
对应到辅助树上就是：
从 x 开始每次，执行以下操作：
将当前节点变为其所处splay的根。
将其变为这棵splay的父亲的右儿子，刚好替换掉原来位于右儿子的节点（对应到原树上就是深度跟需要替换的链一样或更深的节点，它们必定不是更新后的实链上的节点），实现了链的切换。
然后就非常轻松搞定了。
makeroot(x)
一个重要性和access(x)差不多相同的操作。
作用为使得 x 成为 x 所在原树的根，即让 x 成为”吊点“将整棵树吊起来。
那么我们只需要让当前点到根节点成为一条实链，若要使当前点成为根，那么只需要翻转当前点所在实链深度关系即可，其他实链深度关系是不变的。
void makeroot(ll x){
access(x),splay(x),rev(x);
}
findroot(x)
找到 x 所在原树的根。对应到辅助树上就是先access(x)，然后将 x splay为根，那么原树的根就是深度最小的节点。
ll findroot(ll x){
access(x);
splay(x);
pushdown(x);
while(ls(x)) pushdown(x=ls(x));
return x;
}
split(x,y)
将路径 (x,y) 提取出来并进行处理，本题中的处理就是查询路径异或和。
只需要先makeroot(x)，然后access(y)，如果有需要，再splay(y)，这样 y 就储存着路径 (x,y) 的信息了。
如果有必要判断一下 x,y 是否联通，只需要makeroot(x)后findroot(y)判断一下即可。
void split(ll x,ll y){
makeroot(x);
if(findroot(y)!=x){
cout<<"-1\n";
return;
}
access(y),splay(y);
cout< } link(x,y) 连接 (x,y)，若 (x,y) 连通则不进行操作。 makeroot(x)后findroot(y)是否为 x，不是的话直接令 f_x=y 就行了。只要求连通，不一定要变为同一条实链上。 void link(ll x,ll y){ makeroot(x); if(findroot(y)!=x) f[x]=y; } cut(x,y) 删去边 (x,y)，没有则不用删 具体地，makeroot(x) 后判断在辅助树上是否满足这三个条件： 于是代码如下： void cut(ll x,ll y){ makeroot(x); if(findroot(y)==x&&f[x]==y&&!rs(x)) f[x]=ls(y)=0,pushup(y); } findroot(y)的时候就顺便把 y 弄上去了，非常方便。 完整代码 #include #define ll long long #define ls(x) ch[x][0] #define rs(x) ch[x][1] using namespace std; const ll N=3e5+90; ll n,m; ll ch[N][2],sum[N],a[N],f[N]; bool tag[N]; bool get(ll x){ return rs(f[x])==x; } bool isroot(ll x){ return (ls(f[x])!=x)&&(rs(f[x])!=x); } void rev(ll x){ swap(ls(x),rs(x)),tag[x]^=1; } void pushup(ll x){ sum[x]=sum[ls(x)]^sum[rs(x)]^a[x]; } void pushdown(ll x){ if(tag[x]) rev(ls(x)),rev(rs(x)),tag[x]=0; } ll st[N],top; void update(ll x){ if(!isroot(x)) update(f[x]); pushdown(x); return ; } void rotate(ll x){ ll y=f[x],z=f[y]; ll k=get(x); if(!isroot(y)) ch[z][get(y)]=x; ch[y][k]=ch[x][k^1],f[ch[x][k^1]]=y; ch[x][k^1]=y,f[y]=x,f[x]=z; pushup(y),pushup(x); } void splay(ll x){ update(x); // ll u=x; // st[top=1]=u; // while(!isroot(u)) st[++top]=(u=f[u]); // while(top>0) pushdown(st[top--]); while(!isroot(x)){ ll y=f[x]; if(!isroot(y)) rotate(get(x)==get(y) ? y : x); rotate(x); } } void access(ll x){//重点 for(int y=0;x;x=f[y=x]) splay(x),rs(x)=y,pushup(x); } void makeroot(ll x){ access(x),splay(x),rev(x); } ll findroot(ll x){ access(x); splay(x); pushdown(x); while(ls(x)) pushdown(x=ls(x)); return x; } void split(ll x,ll y){ makeroot(x); if(findroot(y)!=x){ cout<<"-1\n"; return; } access(y),splay(y); cout< } void link(ll x,ll y){ makeroot(x); if(findroot(y)!=x) f[x]=y; } void cut(ll x,ll y){ makeroot(x); if(findroot(y)==x&&f[x]==y&&!rs(x)) f[x]=ls(y)=0,pushup(y); } int main(){ // freopen("cin.in","r",stdin); // freopen("cout.out","w",stdout); ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; while(m--){ ll op,x,y; cin>>op>>x>>y; if(op==0) split(x,y); else if(op==1) link(x,y); else if(op==2) cut(x,y); else splay(x),a[x]=y; } return 0; } /* 我去了凭什么炸掉？？？！？！？！？ 还RE什么神经cao */ 练习题 P3203 [HNOI2010] 弹飞绵羊 题意 给定 n 个点，每个点有一个连接系数 k_i，表示点 i 可以跳到点 i+k_i，若有 i+k_i\gt n，则视为跳出。现在给定 m 次操作，每次操作格式为： 1 x，询问点 x 最少需要跳几次才能跳出。 2 x y，将 k_x 改为 y。 ## 思路 假设我们将跳点理解为连边 $(i,i+k_i)$，将跳出理解为连边 $(i,n+1)$，那么很显然这就是一道LCT裸题，它甚至一直只在一棵树上操作。 那么操作 $2$ 们就可以转换为先删边边 $(x,x+k_x)$，再连边 $(x,x+y)$，记得特判一下 $x+k_x,x+y$ 是否大于 $n$ 即可。 对于操作 $1$，在原树上相当于 查询路径 $(x,n+1)$ 的长度，转换到辅助树上就是将 $x$ 转为根后access(n+1)，然后计算 $n+1$ 所处的这棵splay的大小即可，可以用一个 $size$ 数组计算。 ## 代码 ```cpp #include #define ll long long #define ls(x) ch[x][0] #define rs(x) ch[x][1] using namespace std; const ll N=2e5+10; ll ch[N][2],size[N],f[N]; bool tag[N]; ll n,m,a[N]; bool isroot(ll x){ return (ls(f[x])!=x)&&(rs(f[x])!=x); } bool get(ll x){ return rs(f[x])==x; } void rev(ll x){ swap(ls(x),rs(x)),tag[x]^=1; } void pushup(ll x){ size[x]=size[ls(x)]+size[rs(x)]+1; } void pushdown(ll x){ if(tag[x]){ if(ls(x)) rev(ls(x)); if(rs(x)) rev(rs(x)); tag[x]=0; } } void update(ll x){ if(!isroot(x)) update(f[x]); pushdown(x); return ; } void rotate(ll x){ ll y=f[x],z=f[y],k=get(x); if(!isroot(y)) ch[z][get(y)]=x; ch[y][k]=ch[x][k^1],f[ch[x][k^1]]=y; ch[x][k^1]=y,f[y]=x,f[x]=z; pushup(y),pushup(x); return ; } void splay(ll x){ update(x); while(!isroot(x)){ ll y=f[x]; if(!isroot(y)) rotate(get(x)==get(y) ? y : x); rotate(x); } } void access(ll x){ for(int y=0;x;x=f[y=x]) splay(x),rs(x)=y,pushup(x); } ll findroot(ll x){ access(x); splay(x); pushdown(x); while(ls(x)) pushdown(x=ls(x)); return x; } void makeroot(ll x){ access(x); splay(x); rev(x); } void link(ll x,ll y){ makeroot(x); if(findroot(y)!=x) f[x]=y; } void cut(ll x,ll y){ makeroot(x); if(findroot(y)==x&&f[x]==y&&!rs(x)) f[x]=ls(y)=0,pushup(y); } void split(ll x){ makeroot(x); access(n+1); splay(n+1); cout< } ll mkp(ll x,ll y){ return (x+y>n ? n+1 : x+y); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; ll t=mkp(i,a[i]); link(i,t); } // makeroot(n+1); // cout< // for(int i=1;i<=n;i++){ // split(i); // } // cout<<"\n"; cin>>m; while(m--){ ll op,x,y; cin>>op>>x; x++; if(op==1) split(x); else{ cin>>y; // cout< // cout< cut(x,mkp(x,a[x])); link(x,mkp(x,y)); a[x]=y; } } return 0; } ``` # [P4219 [BJOI2014] 大融合](https://www.luogu.com.cn/problem/P4219) 一道很好的帮助更深一步掌握LCT的题。 ## 题意 给定 $n$ 个节点，并给定 $m$ 次操作，操作格式为： - ```A x y``` 连边 $(x,y)$，保证 $(x,y)$ 不连通。 - ```Q x y``` 查询经过边 $(x,y)$ 的简单路径有多少条。 $1\le n,m\le10^5 思路 见连边知LCT。 不难想到，操作二的询问本质上就是cut(x,y)后两棵树大小的乘积。但是这个是子树信息，而LCT主要管理的是路径信息，因此我们要稍微改变一下。于是新增一个 size2(x) 数组表示节点 x 管理的轻儿子的 size 总和，然后考虑在哪里会与 size2 有关系。 update显然要更改为 size[x]=size[ls(x)]+size[rs(x)]+1+size2[x]; 对于splay和rotate，都是在同一棵splay内变化节点的相对位置，对 size2 没影响。 对于access，每次向上跳一棵splay时，根据access的转移，让 size2(x) 加上 size(rs(x))-size(y) 即可。 对于link，我们让一棵splay的根的父亲转变了，这个根节点也变成了它的新父亲的轻儿子，因此令 size2(y)+=size(x) 即可。 对于cut，它只会砍掉splay上的边，没影响。 对于findroot与makeroot，它们都是沿用上述函数的，不用管。 然后就很板子了。 代码 #include #define ll long long #define ls(x) ch[x][0] #define rs(x) ch[x][1] using namespace std; const ll N=1e5+10; ll n,m,ch[N][2],size[N],f[N],size2[N]; bool tag[N]; bool isroot(ll x){ return ls(f[x])!=x&&rs(f[x])!=x; } bool get(ll x){ return rs(f[x])==x; } void pushup(ll x){ size[x]=size[ls(x)]+size[rs(x)]+1+size2[x]; } void rev(ll x){ swap(ls(x),rs(x)),tag[x]^=1; } void pushdown(ll x){ if(tag[x]){ if(ls(x)) rev(ls(x)); if(rs(x)) rev(rs(x)); tag[x]=0; } } void rotate(ll x){ ll y=f[x],z=f[y],k=get(x); if(!isroot(y)) ch[z][get(y)]=x; ch[y][k]=ch[x][k^1],f[ch[x][k^1]]=y; ch[x][k^1]=y,f[y]=x,f[x]=z; pushup(y),pushup(x); return ; } void update(ll x){ if(!isroot(x)) update(f[x]); pushdown(x); return ; } void splay(ll x){ update(x); while(!isroot(x)){ ll y=f[x]; if(!isroot(y)) rotate(get(x)==get(y) ? y : x); rotate(x); } } void access(ll x){ for(int y=0;x;x=f[y=x]) splay(x),size2[x]+=size[rs(x)]-size[y],rs(x)=y,pushup(x); } ll findroot(ll x){ access(x); splay(x); pushdown(x); while(ls(x)) pushdown(x=ls(x)); return x; } void makeroot(ll x){ access(x),splay(x),rev(x); } void link(ll x,ll y){ makeroot(x); if(findroot(y)!=x) f[x]=y,size2[y]+=size[x]; } void cut(ll x,ll y){ makeroot(x); if(findroot(y)==x&&f[x]==y&&!rs(x)) f[x]=ls(y)=0,pushup(y); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; while(m--){ char c; ll x,y; cin>>c>>x>>y; if(c=='A') link(x,y); if(c=='Q'){ cut(x,y); cout< link(x,y); } } return 0; } P2387 [NOI2014] 魔法森林 题意 给定 n 个节点与 m 条边，每条边有两个限制条件 a_i,b_i，要求携带的权值 a 不小于 a_i 且权值 b 不小于 b_i 时才能通过。求一条路径，使得能够从节点 1 到达节点 n，并且满足能够通过这条路径的携带总权值 (a+b) 最小，询问这个最小携带总权值。 ## 思路 首先我们要知道一个操作：用LCT求最小生成树。具体实现就是按边权排序后以边为点连边，若形成环，则不需要这条边。 那么回到这一题上，我们可以尝试运用这种写法。我们将限制条件理解为两种边权，然后按 $a_i$ 升序排序边。然后我们考虑加边后的三种情况： - $1,n$ 不连通且没有环。 这种情况直接进行下一步加边即可，没有影响。 - $1,n$ 连通且没有环 这个时候就要统计一下答案，用LCT将路径 $(1,n)$ split出来处理即可。 - $1,n$ 连通且形成环 如果形成环的话，说明之前的答案我们已经统计过了，那么我们就不用担心这条边对前面答案会有影响。对于这条边形成的这个环上，若这条边不小于这个环边权 $b$ 最大的边，显然这条边是不优的，我们不选择加入。若小于，由于边已经按 $a$ 升序排序，后面的要加入的边的 $a$ 一定是更大的，因此将边权 $b$ 最大的边换为这条边一定是对后面的答案更优的。将边加入后，统计答案，删掉那一条边权 $b$ 最大的边，继续操作即可。 ## 代码 ```cpp #include #define ll long long #define ls(x) ch[x][0] #define rs(x) ch[x][1] #define fi first #define se second #define pll pair //#define make_pair mp using namespace std; const ll N=3e5+90,inf=1e14; ll n,m,w[N],f[N]; ll ch[N][2],mab,ans=inf; pll ps[N]; bool tag[N]; struct edge{ ll x,y,a,b,id; }e[N]; bool cmp(edge a,edge b){ return a.a } bool isroot(ll x){ return ls(f[x])!=x&&rs(f[x])!=x; } bool get(ll x){ return rs(f[x])==x; } void rev(ll x){ swap(ls(x),rs(x)),tag[x]^=1; } void pushup(ll x){ ps[x]=max(make_pair(w[x],x),max(ps[ls(x)],ps[rs(x)])); } void pushdown(ll x){ if(tag[x]){ if(ls(x)) rev(ls(x)); if(rs(x)) rev(rs(x)); tag[x]=0; } } void update(ll x){ if(!isroot(x)) update(f[x]); pushdown(x); return ; } void rotate(ll x){ ll y=f[x],z=f[y],k=get(x); if(!isroot(y)) ch[z][get(y)]=x; ch[y][k]=ch[x][k^1],f[ch[x][k^1]]=y; ch[x][k^1]=y,f[y]=x,f[x]=z; pushup(y),pushup(x); } void splay(ll x){ update(x); while(!isroot(x)){ ll y=f[x]; if(!isroot(y)) rotate(get(x)==get(y) ? y : x); rotate(x); } } void access(ll x){ for(int y=0;x;x=f[y=x]) splay(x),rs(x)=y,pushup(x); } ll findroot(ll x){ access(x); splay(x); pushdown(x); while(ls(x)) pushdown(x=ls(x)); return x; } void makeroot(ll x){ access(x),splay(x),rev(x); } void split(ll x,ll y){ makeroot(x); access(y); splay(y); } void link(ll x,ll y){ makeroot(x); f[x]=y; } void cut(ll x,ll y){ makeroot(x); if(findroot(y)==x&&f[x]==y&&!rs(x)) f[x]=ls(y)=0,pushup(y); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=m;i++) cin>>e[i].x>>e[i].y>>e[i].a>>e[i].b; for(int i=1;i<=n;i++) w[i]=-inf; sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++){ w[i+n]=e[i].b; e[i].id=i; } for(int i=1;i<=m;i++){ if(e[i].x==e[i].y) continue; makeroot(e[i].x); if(findroot(e[i].y)!=e[i].x){ link(e[i].x,e[i].id+n),link(e[i].id+n,e[i].y); } else{ split(e[i].x,e[i].y); if(e[i].b>=ps[e[i].y].fi) continue; ll t=ps[e[i].y].se-n; cut(e[t].x,t+n),cut(t+n,e[t].y); link(e[i].x,e[i].id+n),link(e[i].id+n,e[i].y); } makeroot(1); if(findroot(n)==1){ split(1,n); ans=min(ans,ps[n].fi+e[i].a); } } cout<<(ans<2e6 ? ans : -1); return 0; } ``` # [P1501 [国家集训队] Tree II](https://www.luogu.com.cn/problem/P1501) 一道很好的练手板子题，帮助~~深入~~理解线段树和splay的关系。 ## 题意 ## 思路 ## 代码 ```cpp #include #define ll long long #define ls(x) ch[x][0] #define rs(x) ch[x][1] using namespace std; const ll N=1e5+90,mod=51061; ll n,m,a[N],f[N],w[N]; ll ch[N][2],sum[N],add[N],mul[N],siz[N]; bool tag[N]; void rev(ll x){ swap(ls(x),rs(x)),tag[x]^=1; } void addx(ll x,ll z){ sum[x]=sum[x]*z%mod; add[x]=add[x]*z%mod; mul[x]=mul[x]*z%mod; w[x]=w[x]*z%mod; } void adda(ll x,ll z){ sum[x]=(sum[x]+siz[x]*z%mod)%mod; add[x]=(add[x]+z)%mod; w[x]=(w[x]+z)%mod; } void pushup(ll x){ sum[x]=(sum[ls(x)]+sum[rs(x)]+w[x])%mod; siz[x]=siz[ls(x)]+siz[rs(x)]+1; } ll get(ll x){ return x==rs(f[x]); } bool isroot(ll x){ return rs(f[x])!=x&&ls(f[x])!=x; } void pushdown(ll x){ if(tag[x]) rev(ls(x)),rev(rs(x)),tag[x]=0; addx(ls(x),mul[x]),addx(rs(x),mul[x]); adda(ls(x),add[x]),adda(rs(x),add[x]); add[x]=0,mul[x]=1; } void update(ll x){ if(!isroot(x)) update(f[x]); pushdown(x); return ; } void rotate(ll x){ ll y=f[x],z=f[y]; ll k=get(x); if(!isroot(y)) ch[z][get(y)]=x; ch[y][k]=ch[x][k^1],f[ch[x][k^1]]=y; ch[x][k^1]=y,f[y]=x,f[x]=z; pushup(y),pushup(x); } void splay(ll x){ update(x); while(!isroot(x)){ ll y=f[x]; if(!isroot(y)) rotate(get(x)==get(y) ? y : x); rotate(x); } } void access(ll x){ for(int y=0;x;x=f[y=x]) splay(x),rs(x)=y,pushup(x); } void makeroot(ll x){ access(x),splay(x),rev(x); } ll findroot(ll x){ access(x); splay(x); pushdown(x); while(ls(x)) pushdown(x=ls(x)); return x; } void split(ll x,ll y){ makeroot(x); access(y),splay(y); } void link(ll x,ll y){ makeroot(x); if(findroot(y)!=x) f[x]=y; } void cut(ll x,ll y){ makeroot(x); if(findroot(y)==x&&f[x]==y&&!rs(x)) f[x]=ls(y)=0,pushup(y); } void ad(ll x,ll y,ll z){ split(x,y),adda(y,z); } void mu(ll x,ll y,ll z){ split(x,y),addx(y,z); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // freopen("cin.in","r",stdin); // freopen("cout.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) mul[i]=1,w[i]=1; for(int i=1;i ll x,y; // split(1,1); cin>>x>>y; link(x,y); } while(m--){ char c; ll x,y,z,t; cin>>c>>x>>y; if(c=='+'){ cin>>z; ad(x,y,z); } else if(c=='-'){ cin>>z>>t; cut(x,y),link(z,t); } else if(c=='*'){ cin>>z; mu(x,y,z); } else{ split(x,y); cout< } } return 0; } /* 好板，得写了。 */ ``` # LCT 维护子树（update on 2026.2.8） 虽然说 LCT 只能维护一些链的信息，但是一些简单的子树信息还是能维护一下的。 维护子树信息时，对于一个**辅助树**上的节点，不仅要考虑重边，还要考虑轻边的儿子的信息。即每个轻边儿子的信息都要合并。 简单地说，一个节点的信息包括其所在 splay 树的信息以及轻儿子信息。 然后合并轻儿子时可能出现两种情况： - 轻儿子合并后替换了一个重儿子。 - 轻儿子直接被合并，没有把某个重儿子替换出一个新的轻儿子。 于是可以分别拿 $f_u$ 和 $g_u$ 维护重儿子和轻儿子的信息。 能够维护子树信息是要求其能够差分的。