这是一个数据结构
我们用它来解决动态树问题
注意：LCT不等于动态树
也有一些奇奇怪怪的东西去做动态树
LCT一般要splay，也能fhqtreap吧。。
LCT 能解决的问题
维护一棵树，支持如下操作。
修改两点间路径权值。
查询两点间路径权值和。
修改某点子树权值。
查询某点子树权值和。 唔，看上去是一道树剖模版题。
QAQ
那么我们加一个操作
断开并连接一些边，保证仍是一棵树。
摘自OI WiKi
当然我们需要在线的求出上述问题
那么LCT闪亮登场了
那么，动态树问题是什么呢
字面意思
就是动态的树嘛
一个森林，支持加边删边后还是森林
然后询问一些信息
当然对于某些信息，如果支持离线的话，我们用树剖就能搞定
而我们想在线的去做动态树问题
树剖是怎么做的呢
重链剖分，dfs序
将树变成一条条链转化为序列问题
再在链上套线段树之类的数据结构维护
我们发现树剖是以子树大小做重链剖分
而动态树问题中显然不合适
因为，我们删边加边的操作随时可能改变子树大小
我们在LCT里使用实链剖分
链剖分
重链剖分
我们所谓的树剖，就是重链剖分的常用称呼。对于每个点，我们选择其最大的子树，将这条连边划分为重边，连向其余子树的边化为分轻边。
长链剖分
对每个点选择其深度最大的儿子作为重儿子，连边即为重边，其余作为轻儿子，连边即为轻边。由此得到了若干条互不相交的长链。
实链剖分
同样将某一个儿子的连边为实边，其余儿子的连边为虚边。只不过虚实是可以动态变化的，因此我们需要用更高级、更灵活的数据结构 Splay 来维护每一条实链。
摘自siyuan
LCT基本定义
LCT维护的是一个森林
分为原树与辅助树
辅助树即splay
每一个辅助树为原树中的某一条路径
深度递增且以深度作为排序权值
例如x时原树中y的父亲则辅助树中x可以是y的左儿子，y可以是x的右儿子
对于每一个点，只在一个splay中出现
LCT具体实现
虚实边实现
对于虚边
认父不认子
对于实边
认父认子
f[x]=fa;
s[fa][0/1]=x;
splay相关函数
注意rotate和splay
void pushup(int k){
a[k]=a[s[k][0]]^a[s[k][1]]^v[k];
return ;
}
void change_tag(int k){
tag[k]^=1;
swap(s[k][0],s[k][1]);
return ;
}
void pushdown(int k){
if(!tag[k])return ;
int ls=s[k][0],rs=s[k][1];
change_tag(ls);
change_tag(rs);
tag[k]=0;
return ;
}
void connect(int x,int y,int p){
if(x)f[x]=y;
if(y)s[y][p]=x;
return ;
}
void rotate(int k){
int fa=f[k],ye=f[fa],p1=s[fa][1]==k,p2=s[ye][1]==fa;
f[k]=ye;
if(!isroot(fa))connect(k,ye,p2);
//不能把虚边连实
connect(s[k][p1^1],fa,p1);
connect(fa,k,p1^1);
pushup(fa);
pushup(k);
return ;
}
void splay(int k){
int w=k,tp=0;
st[++tp]=w;
while(!isroot(w))st[++tp]=w=f[w];
while(tp)pushdown(st[tp--]);
//从上往下pushdown完
for(;!isroot(k);rotate(k))
if(!isroot(f[k]))
rotate((s[f[k]][1]==k)==(s[f[f[k]]][1]==f[k])?f[k]:k);
return ;
}
access(k)
‘访问’操作
打通k与原树中k的根之间的路径
使其全部变为实边
void access(int k){
for(int p=0;k;p=k,k=f[k]){
splay(k);//使k为splay中的根节点
s[k][1]=p;//将p到k这条边打实（同时覆盖了原有的实边）
//第一次操作时断开了这一条实边
//使得access之后的这一个splay只存在k到根的这条路径
pushup(k);//更新
}
return ;
}
makeroot(k)
使k成为原树中的根节点
void makeroot(int k){
access(k);//打通路径
splay(k);//将k变成splay中的根
change_tag(k);//使深度翻转，则k点成为深度最小点，且保证中序遍历不变
return ;
}
findroot(k)
找到k在原树中的根节点
int findroot(int k){
access(k);//打通路径，使路径在同一splay中
splay(k);//使k成为splay的根
while(s[k][0]){pushdown(k);k=s[k][0];}
//深度最小的节点即为根，一直往左找即可
splay(k);
return k;
}
split(x,y)
将x到y这条路径提取到一个splay中，并使y成为splay的根
void split(int x,int y){
makeroot(x);//使x成为根
access(y);//打通y到根即y到x的路径
splay(y);//使y成为splay的根
return ;
}
link(x,y)
连边
void link(int x,int y){
makeroot(x);
if(findroot(y)==x)return ;//成环
f[x]=y;//连虚边
return ;
}
cut(x,y)
删边
void cut(int x,int y){
split(x,y);
if(s[y][0]!=x)return ;//x,y之间没有边
f[x]=s[y][0]=0;
pushup(x);
pushup(y);
return ;
}
【模板】Link Cut Tree （动态树）
完整代码
注意主函数
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int tag[maxn],f[maxn],s[maxn][2],a[maxn],v[maxn];
int st[maxn];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
bool isroot(int k){
return s[f[k]][0]!=k&&s[f[k]][1]!=k;
}
void pushup(int k){
a[k]=a[s[k][0]]^a[s[k][1]]^v[k];
return ;
}
void change_tag(int k){
tag[k]^=1;
swap(s[k][0],s[k][1]);
return ;
}
void pushdown(int k){
if(!tag[k])return ;
int ls=s[k][0],rs=s[k][1];
change_tag(ls);
change_tag(rs);
tag[k]=0;
return ;
}
void connect(int x,int y,int p){
if(x)f[x]=y;
if(y)s[y][p]=x;
return ;
}
void rotate(int k){
int fa=f[k],ye=f[fa],p1=s[fa][1]==k,p2=s[ye][1]==fa;
f[k]=ye;
if(!isroot(fa))connect(k,ye,p2);
connect(s[k][p1^1],fa,p1);
connect(fa,k,p1^1);
pushup(fa);
pushup(k);
return ;
}
void splay(int k){
int w=k,tp=0;
st[++tp]=w;
while(!isroot(w))st[++tp]=w=f[w];
while(tp)pushdown(st[tp--]);
for(;!isroot(k);rotate(k))
if(!isroot(f[k]))
rotate((s[f[k]][1]==k)==(s[f[f[k]]][1]==f[k])?f[k]:k);
return ;
}
void access(int k){
for(int p=0;k;p=k,k=f[k]){
splay(k);
s[k][1]=p;
pushup(k);
}
return ;
}
void makeroot(int k){
access(k);
splay(k);
change_tag(k);
return ;
}
int findroot(int k){
access(k);
splay(k);
while(s[k][0]){
pushdown(k);
k=s[k][0];
}
splay(k);
return k;
}
void split(int x,int y){
makeroot(x);
access(y);
splay(y);
return ;
}
void link(int x,int y){
makeroot(x);
if(findroot(y)==x)return ;
f[x]=y;
return ;
}
void cut(int x,int y){
split(x,y);
if(s[y][0]!=x)return ;
f[x]=s[y][0]=0;
pushup(x);
pushup(y);
return ;
}
int main(){
int n,m;
n=read();m=read();
for(int i=1;i<=n;i++)v[i]=read();
for(int i=1;i<=m;i++){
int opt,x,y;
opt=read();x=read();y=read();
if(opt==0){
split(x,y);printf("%d\n",a[y]);
}
else if(opt==1)link(x,y);
else if(opt==2)cut(x,y);
else{
splay(x);
//一定要让x变成splay的根再改权值
//否则有pushup不到的可能
v[x]=y;
}
}
return 0;
}
LCT的应用
1.LCT动态维护最小生成树
最小生成树大家应该都会kruscal或者prim什么的
但如果这个图一直删边就比较痛苦了
没关系
LCT可以帮我们解决这个问题
对于这个算法的实现大致如下
将边也建成点，连(u,v)时link(u,edge),link(v,edge)
边权变为LCT中的点权
LCT维护splay中的最大点权和最大点权的点的编号
没出现环之前一直连，出现了环就比较最大的边权看是否删掉最大边再加边
然后因为对于删边使头疼的
我们考虑离线
倒序操作加边
看一道题目
[WC2006]水管局长
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005,maxm=100005,maxq=100005;
struct edge{
int x,y,z;
}e[maxn+maxm];
int n,m,q;
int tag[maxn+maxm];
int mx[maxn+maxm],pos[maxn+maxm],val[maxn+maxm];
int f[maxn+maxm],s[maxn+maxm][2];
int id[maxn][maxn],dis[maxn][maxn];
int st[maxn+maxm];
int opt[maxq],u[maxq],v[maxq];
int ans[maxq];
bool vis[maxn][maxn];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
bool isroot(int k){
return s[f[k]][0]!=k&&s[f[k]][1]!=k;
}
void change_tag(int k){
if(!k)return ;
swap(s[k][0],s[k][1]);
tag[k]^=1;
return ;
}
void pushup(int k){
mx[k]=max(max(mx[s[k][0]],mx[s[k][1]]),val[k]);
if(mx[k]==mx[s[k][0]])pos[k]=pos[s[k][0]];
else if(mx[k]==mx[s[k][1]])pos[k]=pos[s[k][1]];
else pos[k]=k;
return ;
}
void pushdown(int k){
if(!tag[k])return ;
change_tag(s[k][0]);
change_tag(s[k][1]);
tag[k]=0;
return ;
}
void connect(int x,int y,int z,bool bj){
if(y&&bj)s[y][z]=x;
if(x)f[x]=y;
return ;
}
void rotate(int k){
int fa=f[k],ye=f[fa];
int p1=s[fa][1]==k,p2=s[ye][1]==fa;
int son=s[k][p1^1];
connect(k,ye,p2,!isroot(fa));
connect(fa,k,p1^1,1);
connect(son,fa,p1,1);
pushup(fa);
pushup(k);
return ;
}
void splay(int k){
int w=k,tp=0;
st[++tp]=w;
while(!isroot(w)){
st[++tp]=f[w];
w=f[w];
}
while(tp)
pushdown(st[tp--]);
for(;!isroot(k);rotate(k))
if(!isroot(f[k]))
rotate((s[f[k]][1]==k)==(s[f[f[k]]][1]==f[k])?f[k]:k);
pushup(k);
return ;
}
int access(int k){
int p;
for(p=0;k;p=k,k=f[k]){
splay(k);
s[k][1]=p;
pushup(k);
}
return p;
}
void makeroot(int k){
access(k);
splay(k);
change_tag(k);
return ;
}
int findroot(int k){
access(k);
splay(k);
while(s[k][0]){pushdown(k);k=s[k][0];}
splay(k);
return k;
}
void split(int x,int y){
makeroot(x);
access(y);
splay(y);
return ;
}
void link(int x,int y){
makeroot(x);
if(findroot(y)==x)return ;
f[x]=y;
return ;
}
void cut(int x,int y){
makeroot(x);
if(findroot(y)!=x||f[y]!=x||s[y][0])return ;
f[y]=0;
s[x][1]=0;
pushup(x);
return ;
}
void addedge(int x,int y,int t,int id){
if(findroot(x)!=findroot(y)){
link(x,id);
link(y,id);
}
else{
split(x,y);
int dist=mx[y];
if(dist<=t)return ;
int p=pos[y];
cut(e[p].x,p);
cut(e[p].y,p);
link(x,id);
link(y,id);
}
return ;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
n=read();m=read();q=read();
for(int i=1;i<=m;i++){
int x,y,t;
x=read();y=read();t=read();
if(y<x)swap(x,y);
e[i+n].x=x;e[i+n].y=y;e[i+n].z=t;
id[x][y]=id[y][x]=i+n;
dis[x][y]=dis[y][x]=t;
val[i+n]=t;
}
for(int i=1;i<=q;i++){
opt[i]=read();
u[i]=read();
v[i]=read();
if(v[i]<u[i])swap(u[i],v[i]);
if(opt[i]==2)
vis[u[i]][v[i]]=1;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(vis[i][j]||(!id[i][j]))continue;
addedge(i,j,dis[i][j],id[i][j]);
}
}
int tot=0;
for(int i=q;i>=1;i--){
int x=u[i],y=v[i];
if(opt[i]==2)
addedge(x,y,dis[x][y],id[x][y]);
else{
split(x,y);
ans[++tot]=mx[y];
}
}
for(int i=tot;i>=1;i--)
printf("%d\n",ans[i]);
return 0;
}
