Link-Cut-Tree 学习笔记

Link-Cut-Tree 是著名的 Tarjan 教授发明的数据结构，利用动态树，我们珂以解决很多复杂的树上操作。

先看一道例题：严格次小生成树

有人会问了，这不是裸的树上倍增吗？

我想说的是，树上倍增你不嫌麻烦吗？

于是我们拿出强有力的武器 —— Link-Cut-Tree

我们要实现动态连边，动态查询路径最大值次大值。

如何操作？

#include<cstdio>
#include<algorithm>
#define N 2919810
#define int long long
using namespace std;
int n,m,f[N],ans=1e21,res;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
struct edge{
	int u,v,w,vis;
	void in(){scanf("%lld%lld%lld",&u,&v,&w);}
	bool operator<(const edge &e)const{return w<e.w;}
}e[N];
struct link_cut_tree{
	int ch[N][2],f[N],val[N],mx1[N],mx2[N],st[N];
	bool r[N];
	#define lc ch[x][0]
	#define rc ch[x][1]
	void pushup(int x){
		mx1[x]=val[x];
    	if(mx1[x]<mx1[lc])mx2[x]=mx1[x],mx1[x]=mx1[lc];
    	else if(mx1[x]>mx1[lc])mx2[x]=max(mx2[x],mx1[lc]);
    	if(mx1[x]<mx1[rc])mx2[x]=mx1[x],mx1[x]=mx1[rc];
    	else if(mx1[x]>mx1[rc])mx2[x]=max(mx2[x],mx1[rc]);
    	mx2[x]=max(max(mx2[x],mx2[rc]),mx2[lc]);
	}
	int son(int x){return ch[f[x]][1]==x;}
	int nroot(int x){return x==ch[f[x]][0]||x==ch[f[x]][1];}
	void rev(int x){swap(lc,rc),r[x]^=1;}
	void pushdown(int x){
		if(r[x]){
			if(lc)rev(lc);
			if(rc)rev(rc);
			r[x]=0;
		}
	}
	void rotate(int x){
		int y=f[x],z=f[y],k=son(x),w=ch[x][!k];
		if(nroot(y))ch[z][son(y)]=x;
		ch[x][!k]=y,ch[y][k]=w;
		if(w)f[w]=y;
		f[x]=z,f[y]=x;
		pushup(y);
	}
	void splay(int x){
		int y=x,z=0;
		st[++z]=y;
		while(nroot(y))st[++z]=y=f[y];
		while(z)pushdown(st[z--]);
		while(nroot(x)){
			y=f[x];
			if(nroot(y))rotate(son(x)!=son(y)?x:y);
			rotate(x);
		}
		pushup(x);
	}
	void access(int x){for(int y=0;x;x=f[y=x])splay(x),rc=y,pushup(x);}
	void makeroot(int x){access(x);splay(x);rev(x);}
	void split(int x,int y){makeroot(x);access(y);splay(y);}
	void link(int x,int y){makeroot(x);f[x]=y;}
	void cut(int x,int y){split(x,y);f[x]=ch[y][0]=0;pushup(y);}
}lct;
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)e[i].in();
	sort(e+1,e+m+1);
	for(int i=1;i<=n+m;i++)f[i]=i;
	int cnt=0;
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)==find(v))continue;
		e[i].vis=1;lct.val[i+n]=e[i].w;
		lct.link(u,i+n);lct.link(i+n,v);
		f[find(u)]=find(v),res+=w;
		if(++cnt==n-1)break;
	}
	for(int i=1;i<=m;i++){
		if(e[i].vis)continue;
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(u==v)continue;
		lct.split(u,v);
		int val=lct.mx1[v],v2=lct.mx2[v];
		int now=res-val+w,now2=res-v2+w;
		if(now>res)ans=min(ans,now);
		else if(now2>res)ans=min(ans,now2);
	}
	printf("%lld",ans);
	//if(ans>=2147483647)return puts("-1"),0;
	return 0;
}

先给出代码，底下这个像 kruskal 的部分就是我们的对于本题的操作，我们先具体看 LCT 的操作。

struct link_cut_tree{
	int ch[N][2],f[N],val[N],mx1[N],mx2[N],st[N];
	bool r[N];
	#define lc ch[x][0]
	#define rc ch[x][1]
	void pushup(int x){
		mx1[x]=val[x];
    	if(mx1[x]<mx1[lc])mx2[x]=mx1[x],mx1[x]=mx1[lc];
    	else if(mx1[x]>mx1[lc])mx2[x]=max(mx2[x],mx1[lc]);
    	if(mx1[x]<mx1[rc])mx2[x]=mx1[x],mx1[x]=mx1[rc];
    	else if(mx1[x]>mx1[rc])mx2[x]=max(mx2[x],mx1[rc]);
    	mx2[x]=max(max(mx2[x],mx2[rc]),mx2[lc]);
	}
	int son(int x){return ch[f[x]][1]==x;}
	int nroot(int x){return x==ch[f[x]][0]||x==ch[f[x]][1];}
	void rev(int x){swap(lc,rc),r[x]^=1;}
	void pushdown(int x){
		if(r[x]){
			if(lc)rev(lc);
			if(rc)rev(rc);
			r[x]=0;
		}
	}
	void rotate(int x){
		int y=f[x],z=f[y],k=son(x),w=ch[x][!k];
		if(nroot(y))ch[z][son(y)]=x;
		ch[x][!k]=y,ch[y][k]=w;
		if(w)f[w]=y;
		f[x]=z,f[y]=x;
		pushup(y);
	}
	void splay(int x){
		int y=x,z=0;
		st[++z]=y;
		while(nroot(y))st[++z]=y=f[y];
		while(z)pushdown(st[z--]);
		while(nroot(x)){
			y=f[x];
			if(nroot(y))rotate(son(x)!=son(y)?x:y);
			rotate(x);
		}
		pushup(x);
	}
	void access(int x){for(int y=0;x;x=f[y=x])splay(x),rc=y,pushup(x);}
	void makeroot(int x){access(x);splay(x);rev(x);}
	void split(int x,int y){makeroot(x);access(y);splay(y);}
	void link(int x,int y){makeroot(x);f[x]=y;}
	void cut(int x,int y){split(x,y);f[x]=ch[y][0]=0;pushup(y);}
}lct;

怎么样？是不是很短？

pushup 操作在这里是用来维护最大值和次大值的，因题而异。

在一些题里，区间修改需要修改 pushdown 操作，将会在下一个例题讲解。

首先，rotate 操作我们是必须会的，具体就是把 xx 和 yy 换位置。

这里不再赘述。

splay 操作和普通平衡树一样，只是要先把访问的点 pushdown 了，我们手动模拟一个栈即可，也可以靠深搜来完成。

access 操作是打通一个点到根的路径，就是将该点到根的路径变成实链。 我们只需要不断的吧x翻转到当前根再连上之前的点，这样就可以不断向上访问，根节点之后不存在节点，循环也会自动退出。

makeroot 很好理解，打通当前点，splay 一下，把当前点所在的splay的根换成当前点，然后翻转区间保证平衡性。

split 操作就是把 xx 设为根，然后再把 yy 打通根，最后把 yy 搞成根节点。

link 操作和 cut 操作具体实现要看有没有重复边，一般情况可以直接使用我的代码。

剩下的例题咕咕咕