标签：faz LCT return lc int void 笔记学习 rc

\(\text{LCT}\) 学习笔记

可曾久仰 \(\text{LCT}\) 大名，可曾听闻 \(\text{Splay}\) 骂名？

动态树

对于一棵有 \(n\) 个节点的树，如果每个点都有点权，那么求解 \(x,y\) 之间的路径上的点权和可以用树链剖分+线段树简单做到。

考虑对于一棵 \(n\) 个节点的动态树，也就是可以删除某一条边或者加入某一条边。那么此时我们的树链所保证的时间复杂度可能不再正确，因此我们需要一种动态保证时间复杂度的划分方法，我们称之为 实链剖分。

实链剖分：

对每一条边钦定实或虚两种，每一个节点最多只有一条与儿子相连的边为实边，其余均为虚边。不同于重链剖分和长链剖分，因为实链剖分的应用场景在于一棵变化的树，因此实边和虚边的划分没有具体的要求。

如何正确的钦定实链虚链从而达到正确的时间复杂度就是所谓的 \(\text{LCT}\)。

\(\text{LCT}\)

我们考虑用 \(\text{Splay}\) 维护每一个剖分出的实链，并且将这些 \(\text{Splay}\) 合并到一棵树里用来代替原先森林里的每一棵树。更具体的，这棵辅助树有以下性质：

原图中的每一棵树都对应一棵辅助树，原图中不联通的两个点不会出现在一棵辅助树上。
辅助树中的每一棵 \(\text{Splay}\) 树的中序遍历都对应在原树上一条从上到下的链。
原树中的节点和辅助树中的节点一一对应。
辅助树中的每一棵 \(\text{Splay}\) 树并不孤立。对于每一棵 \(\text{Splay}\) 树的根节点，其对应在辅助树上的父亲即为原树中其对应链顶的父亲。区别于 \(\text{Splay}\) 树内的实边，\(\text{Splay}\) 树根节点的父亲边在原树中是一条虚边。为了区别这两种边，我们考虑让每一个节点只维护实边相连的儿子节点，如此我们可以在正常向上跳父亲的同时区分实边和虚边。
通过上面的性质，我们可以看出每一棵辅助树都对应唯一的原树和剖分方式，因此我们只需要维护辅助树即可。

因为需要用到 \(\text{Splay}\)，所以介绍 \(\text{Splay}\) 的操作函数（部分）：

\(\text{IsRoot}\)

bool IsRoot(int x){
    return lc(faz[x])==x||rc(faz[x])==x;
    //因为 LCT 的虚边认父不认子，因此只要某个点的父亲节点没有它作为儿子，那么它一定是 Splay 的根
}//注意这个函数不是根时返回 1，是根时返回 0

\(\text{Rotate}\)

void Rotate(int x){
    int y=faz[x],z=faz[y],k=get(x);//get 表示 x 是左儿子(返回 0)还是右儿子(返回 1)
    if(IsRoot(y))ch[z][get(y)]=x;//不是根的话需要维护实边的儿子信息
    ch[y][k]=ch[x][!k],faz[ch[x][!k]]=y;
    ch[x][!k]=y,faz[y]=x,faz[x]=z;
    PushUp(y),PushUp(x);//PushUp 就是上传答案的函数
    return ;
}

\(\text{Splay}\)

void Splay(int x){
    for(int y;y=faz[x],IsRoot(x);Rotate(x)){
        if(IsRoot(y))Rotate(get(y)==get(x)?y:x);
    }
    return ;
}//普通的双旋 Splay

考虑如何通过辅助树完成对答案的求解。因为对于一棵变化的树来讲，通过多条链的信息合并答案显然是困难的，因此可以考虑将 \(x,y\) 之间的路径钦定为一条实链，这样我们便只需要维护每一条链的信息并直接查询即可。为了让 \(x,y\) 之间的路径是一种合法的划分方式，我们首先需要将 \(x\) 换到原树的根部。不难发现我们可以通过打通 \(x\) 到当前根部的路径，最后整体翻转，这样原本深度最低的 \(x\) 就变成深度最高的节点了。打通的链一定只保留了所进入的每一条实链的位置 \(x\) 到其链顶的所有点，也就是中序遍历在 \(x\) 之前的点，那么我们只需要将 \(x\) 换到当前 \(\text{Splay}\) 树的顶部，所需要的就只有 \(x\) 的左子树了。

考虑实现这个过程的函数：

\(\text{Access}\)

void Access(int x){
    for(int y=0;x;x=faz[y=x]){//相当于向上跳链
        Splay(x),rc(x)=y;//将 x 旋到 Splay 顶，只需要保留左子树，右子树是上一个跳到的节点
        PushUp(x);//更新信息
    }
    return ;
}

\(\text{PushTag}\)

void PushTag(int x){
    swap(lc(x),rc(x));//因为打上了标记，所以中序遍历是颠倒的，需要交换左右子树
    tag[x]^=1;
    return ;
}

\(\text{MakeRoot}\)

void MakeRoot(int x){
    Access(x),Splay(x);//打通路径并让 x 维护整条链的信息
    PushTag(x);//整体翻转
    return ;
}

不难看出因为有了反转标记，所以在将某个点旋到顶部之前需要将所有标记下放，因此需要添加函数：

\(\text{PushDown}\)

void PushDown(int x){
    if(tag[x]){
        if(lc(x))PushTag(lc(x));
        if(rc(x))PushTag(rc(x));
        tag[x]=0;
    }
    return ;
}

\(\text{Update}\)

void Update(int x){
    if(IsRoot(x))Update(faz[x]);//优先下放父亲的标记
    PushDown(x);
    return ;
}
void Splay(int x){
    Update(x);
    ...
}

这样我们就将 \(x\) 换到了根部，接着打通 \(x,y\) 之间的路径即可得到答案。

实现操作的函数：

\(\text{Split}\)

void Split(int x,int y){
    MakeRoot(x);
    Access(y),Splay(y);
}//注意这个函数将 x,y 之间的路径分割出来后，信息存储在 y 处

那么我们已经考虑完了如何查询题目中给出的询问，但是我们依旧没有考虑如何添加一条边或是删去一条边。考虑相同的思路，我们在 \(x,y\) 之间加边的时候，首先要考虑此次加边是否合法，因此我们需要知道每个点所在的辅助树的根节点。如果两个点在同一个辅助树中，说明他们原先就已经联通，不可以继续加边；否则不妨在 \(x,y\) 之间连接一条虚边。

而对于删边，首先要考虑 \(x,y\) 之间是否已经有边存在，我们将 \(x\) 换到根之后，如果 \(x,y\) 不在同一个辅助树，或者 \(y\) 的父亲不是 \(x\)，或者 \(y\) 不是所在实链的链顶，那么说明 \(x,y\) 之间没有边，不可以删边；不然将 \(x\) 的右儿子和 \(y\) 的父亲清空即可。

实现操作的函数：

\(\text{Link}\)

void Link(int x,int y){
    MakeRoot(x);
    if(FindRoot(y)==x)return ;//如果保证加边合法，则这句话可以去掉。
    faz[x]=y;
    return ;
}

\(\text{Cut}\)

void Cut(int x,int y){
    MakeRoot(x);
    if(FindRoot(y)!=x||faz[y]!=x||lc(y))return ;
    //如果保证删边合法，则可以删掉，但必须保留 FindRoot，不然无法保证正确性
    rc(x)=faz[y]=0;
    return ;
}

以上就是 \(\text{LCT}\) 的全部函数实现。对于一个 \(n\) 个点 \(m\) 次操作的 \(\text{LCT}\)，其时间复杂度是 \(O((n+m)\log n)\) 的。

做题技巧

区间下放

有认真学习过 \(\text{Splay}\) 的人一定知道，对一个区间建立区间 \(\text{Splay}\)，我们可以通过区间标记的方式维护一些内容。更具体的，类似于区间和，区间最大（小）值，区间加，区间乘等一些常见的线段树标记都可以在 \(\text{LCT}\) 上进行维护和下放，只需要多使用一个类似于 \(\text{PushTag}\) 的函数，并将这些函数在 \(\text{PushDown}\) 内统一调用即可。（注意函数调用的顺序）

普通 \(\text{LCT}\)

这里普通的定义指：

权值在点上，也就是操作的修改和查询仅关于点权。
修改和查询仅查询链相关内容。

对于这样的问题，可以用上面讲解的模板简单通过。

【模板】LCT

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int n,m;
namespace LCT{
	#define lc(x) ch[x][0]
	#define rc(x) ch[x][1]
	#define get(x) (rc(faz[x])==x)
	int faz[N],ch[N][2],sum[N],val[N];
	bool tag[N];
	bool IsRoot(int x){
		return lc(faz[x])==x||rc(faz[x])==x;
	}
	void PushUp(int x){
		sum[x]=sum[lc(x)]^sum[rc(x)]^val[x];
		return ;
	}
	void PushTag(int x){
		swap(lc(x),rc(x));
		tag[x]^=1;
		return ;
	}
	void PushDown(int x){
		if(tag[x]){
			if(lc(x))PushTag(lc(x));
			if(rc(x))PushTag(rc(x));
			tag[x]=0;
		}
		return ;
	}
	void Rotate(int x){
		int y=faz[x],z=faz[y],k=get(x);
		if(IsRoot(y))ch[z][get(y)]=x;
		ch[y][k]=ch[x][!k],faz[ch[x][!k]]=y;
		ch[x][!k]=y,faz[y]=x,faz[x]=z;
		PushUp(y),PushUp(x);
		return ;
	}
	void Update(int x){
		if(IsRoot(x))Update(faz[x]);
		PushDown(x);
		return ;
	}
	void Splay(int x){
		Update(x);
		for(int y;y=faz[x],IsRoot(x);Rotate(x)){
			if(IsRoot(y))Rotate(get(y)==get(x)?y:x);
		}
		return ;
	}
	void Access(int x){
		for(int y=0;x;x=faz[y=x]){
			Splay(x),rc(x)=y;
			PushUp(x); 
		}
		return ;
	}
	void MakeRoot(int x){
		Access(x),Splay(x);
		PushTag(x);
		return ;
	}
	int FindRoot(int x){
		Access(x),Splay(x);
		while(lc(x))PushDown(x),x=lc(x);
		Splay(x);
		return x;
	}
	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 ;
		faz[x]=y;
		return ;
	}
	void Cut(int x,int y){
		MakeRoot(x);
		if(FindRoot(y)!=x||faz[y]!=x||lc(y))return ;
		faz[y]=rc(x)=0;
		return ;
	}
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>LCT::val[i];
	while(m--){
		int opt,x,y;
		cin>>opt>>x>>y;
		switch(opt){
			case 0:{
				LCT::Split(x,y);
				cout<<LCT::sum[y]<<"\n";
				break;
			}case 1:{
				LCT::Link(x,y);
				break;
			}case 2:{
				LCT::Cut(x,y); 
				break;
			}case 3:{
				LCT::Splay(x);
				LCT::val[x]=y;
				break;
			}
		}
	}
	return 0;
}

边权 \(\text{LCT}\)

顾名思义，这类 \(\text{LCT}\) 相当于将题目中的点权转为了边权。因为 \(\text{LCT}\) 没有固定的父子关系，因此维护的边权会变得紊乱，可能会出现一个点需要维护多个边权的情况。因此我们考虑拆点，将 \(u\to v\) 拆成 \(u\to w\to v\)，然后让 \(w\) 的点权成为边 \(u\to v\) 的边权，如此即可正确求解。当然对于某一些特定的题目，我们也可以采取固定原始树的形状后，将边权下放到儿子节点的方式。

【SPOJ375 QTREE】难存的情缘

#include <bits/stdc++.h>
using namespace std;

const int N=2e4+5,inf=2e9;

int T,n;
namespace LCT{
	#define lc(x) (ch[x][0])
	#define rc(x) (ch[x][1])
	#define get(x) (rc(faz[x])==x)
	int ch[N][2],faz[N],val[N],mx[N],mn[N];
	bool tag[N];
	void Init(){
		for(int i=0;i<(n<<1);i++){
			mx[i]=-inf;
			mn[i]=val[i]=inf;
		}
		return ;
	}
	bool IsRoot(int x){
		return lc(faz[x])==x||rc(faz[x])==x;
	}
	void PushUp(int x){
		mx[x]=max({mx[lc(x)],mx[rc(x)],(abs(val[x])==inf?-inf:val[x])});
		mn[x]=min({mn[lc(x)],mn[rc(x)],(abs(val[x])==inf?inf:val[x])});
		return ;
	}
	void PushTag(int x){
		swap(lc(x),rc(x));
		tag[x]^=1;
		return ;
	}
	void PushDown(int x){
		if(tag[x]){
			if(lc(x))PushTag(lc(x));
			if(rc(x))PushTag(rc(x));
			tag[x]=0;
		}
		return ;
	}
	void Rotate(int x){
		int y=faz[x],z=faz[y],k=get(x);
		if(IsRoot(y))ch[z][get(y)]=x;
		ch[y][k]=ch[x][!k],faz[ch[x][!k]]=y;
		ch[x][!k]=y,faz[y]=x,faz[x]=z;
		PushUp(y),PushUp(x);
		return ;
	}
	void Update(int x){
		if(IsRoot(x))Update(faz[x]);
		PushDown(x);
		return ;
	}
	void Splay(int x){
		Update(x);
		for(int y;y=faz[x],IsRoot(x);Rotate(x)){
			if(IsRoot(y))Rotate(get(y)==get(x)?y:x); 
		}
		return ;
	}
	void Access(int x){
		for(int y=0;x;x=faz[y=x]){
			Splay(x),rc(x)=y;
			PushUp(x);
		}
		return ;
	}
	void MakeRoot(int x){
		Access(x),Splay(x);
		PushTag(x);
		return ;
	}
	void Split(int x,int y){
		MakeRoot(x);
		Access(y),Splay(y);
		return ;
	} 
	void Link(int x,int y){
		MakeRoot(x);
		faz[x]=y;
		return ;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	LCT::Init();
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		LCT::val[n+i]=z;
		LCT::Link(x,n+i);
		LCT::Link(n+i,y);
	}
	while(1){
		string s; 
		cin>>s;
		if(s[0]=='D')break;
		int x,y;
		cin>>x>>y;
		switch(s[0]){
			case 'C':{
				LCT::MakeRoot(n+x);
				LCT::val[n+x]=y;
				break;
			}case 'Q':{
				LCT::Split(x,y);
				cout<<LCT::mx[y]<<"\n";
				break;
			}
		}
	}
	return 0;
}

子树 \(\text{LCT}\)

对于题目中的操作涉及子树查询时，我们发现仅通过一条链的信息没有办法维护子树的信息，但我们不妨对每一个节点多统计一个信息：虚子树的信息。也就是每个点通过虚边相连的点的信息汇总。那么我们在 \(\text{PushUp}\) 时也需要加入这些虚子树的贡献才能得到正确的答案。

同时考虑到在 \(\text{Access}\) 时，我们更改了一个节点的右节点，同样修改的还有虚节点的信息，因此我们需要对该函数进行一些处理，更具体的，我们需要加入

siz2[x]+=siz[rc(x)]-siz[y];

作为信息的更新，正确性显然。同理在 \(\text{Link}\) 时，我们也添加了一条虚边，因此 \(x\) 的贡献需要加给 \(y\)。

值得注意的是，当维护的信息不具有可减性时（最大值），我们需要通过其他的数据结构维护。

【BJOI2014】大融合

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

const int N=3e4+5,Q=4e4+5;

int n,m,tot;
int fa[N],ans[Q];
map<pii,bool>mp;
struct Query{
	int opt,l,r;
}q[Q];

int FindFaz(int x){
	if(fa[x]==x)return fa[x];
	return fa[x]=FindFaz(fa[x]);
}

void Merge(int x,int y){
	int a=FindFaz(x),b=FindFaz(y);
	if(a!=b)fa[a]=b;
	return ;
}

namespace LCT{
	#define faz(x) FindFaz(faz[x])
	#define lc(x) (ch[x][0])
	#define rc(x) (ch[x][1])
	#define get(x) (rc(faz(x))==x)
	int faz[N],ch[N][2],siz[N];
	bool tag[N];
	void Init(int x){
		lc(x)=rc(x)=0;
		siz[x]=1;
		return ;
	}
	bool IsRoot(int x){
		return lc(faz(x))==x||rc(faz(x))==x;
	}
	void PushUp(int x){
		siz[x]=siz[lc(x)]+siz[rc(x)]+1;
		return ;
	}
	void PushTag(int x){
		swap(lc(x),rc(x));
		tag[x]^=1;
		return ;
	}
	void PushDown(int x){
		if(tag[x]){
			if(lc(x))PushTag(lc(x));
			if(rc(x))PushTag(rc(x));
			tag[x]=0; 
		}
		return ;
	}
	void Rotate(int x){
		int y=faz(x),z=faz(y),k=get(x);
		if(IsRoot(y))ch[z][get(y)]=x;
		ch[y][k]=ch[x][!k],faz[ch[x][!k]]=y;
		ch[x][!k]=y,faz[y]=x,faz[x]=z;
		PushUp(y),PushUp(x);
		return ;
	}
	void Update(int x){
		if(IsRoot(x))Update(faz(x));
		PushDown(x);
		return ;
	}
	void Splay(int x){
		Update(x);
		for(int y;y=faz(x),IsRoot(x);Rotate(x)){
			if(IsRoot(y))Rotate(get(y)==get(x)?y:x);
		}
		return ;
	}
	void Access(int x){
		for(int y=0;x;x=faz(y=x)){
			Splay(x),rc(x)=y;
			PushUp(x);
		}
		return ;
	}
	void MakeRoot(int x){
		Access(x),Splay(x);
		PushTag(x);
		return ;
	}
	int FindRoot(int x){
		Access(x),Splay(x);
		while(lc(x))PushDown(x),x=lc(x);
		Splay(x);
		return x;
	}
	void Split(int x,int y){
		MakeRoot(x);
		Access(y),Splay(y);
		return ;
	}
	void Dfs(int x){
		PushDown(x);
		if(lc(x))Dfs(lc(x)),Merge(lc(x),x);
		if(rc(x))Dfs(rc(x)),Merge(rc(x),x);
		return ;
	}
	void Link(int x,int y){
		int a=FindFaz(x),b=FindFaz(y);
		if(FindRoot(a)==FindRoot(b)){
			Split(a,b);
			Dfs(b);
			int t=FindFaz(b);
			faz[t]=faz(b);
			Init(t);
		}else{
			MakeRoot(a);
			faz[a]=b;
		}
		return ;
	}
	int Query(int x,int y){
		int a=FindFaz(x),b=FindFaz(y);
		Split(a,b);
		return siz[b]-1;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		mp[{x,y}]=mp[{y,x}]=true;
	}
	while(1){
		int opt,x,y;
		cin>>opt;
		if(opt==-1)break;
		cin>>x>>y;
		q[++tot]={opt,x,y};
		if(opt==0)mp[{x,y}]=mp[{y,x}]=false;
	}
	for(auto it=mp.begin();it!=mp.end();it++){
		if(it->second){
			int x=it->first.first,y=it->first.second;
			mp[{x,y}]=mp[{y,x}]=false;
			LCT::Link(x,y);
		}
	}
	for(int i=tot;i>=1;i--){
		int x=q[i].l,y=q[i].r;
		if(q[i].opt==0)LCT::Link(x,y);
		else ans[i]=LCT::Query(x,y);
	}
	for(int i=1;i<=tot;i++){
		if(q[i].opt)cout<<ans[i]<<"\n";
	}
	return 0;
}

图论 \(\text{LCT}\)

当然了，我们的 \(\text{LCT}\) 不仅仅适用于树论，对于图论，\(\text{LCT}\) 也有一战之力。

维护联通性

显然当 \(\text{FindRoot}(x)=\text{FindRoot(y)}\) 时两个点联通。当然需要保证图始终是森林或不支持删边。

【SDOI2008】洞穴勘测

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+5;

int n,m;
namespace LCT{
	#define lc(x) ch[x][0]
	#define rc(x) ch[x][1]
	#define get(x) (rc(faz[x])==x)
	int faz[N],ch[N][2];
	bool tag[N];
	bool IsRoot(int x){
		return lc(faz[x])==x||rc(faz[x])==x;
	}
	void PushTag(int x){
		swap(lc(x),rc(x));
		tag[x]^=1;
		return ;
	}
	void PushDown(int x){
		if(tag[x]){
			if(lc(x))PushTag(lc(x));
			if(rc(x))PushTag(rc(x));
			tag[x]=0;
		}
		return ;
	}
	void Rotate(int x){
		int y=faz[x],z=faz[y],k=get(x);
		if(IsRoot(y))ch[z][get(y)]=x;
		ch[y][k]=ch[x][!k],faz[ch[x][!k]]=y;
		ch[x][!k]=y,faz[y]=x,faz[x]=z;
		return ;
	}
	void Update(int x){
		if(IsRoot(x))Update(faz[x]);
		PushDown(x);
		return ;
	}
	void Splay(int x){
		Update(x);
		for(int y;y=faz[x],IsRoot(x);Rotate(x)){
			if(IsRoot(y))Rotate(get(y)==get(x)?y:x);
		}
		return ;
	}
	void Access(int x){
		for(int y=0;x;x=faz[y=x])Splay(x),rc(x)=y;
		return ;
	}
	void MakeRoot(int x){
		Access(x),Splay(x);
		PushTag(x);
		return ;
	}
	int FindRoot(int x){
		Access(x),Splay(x);
		while(lc(x))PushDown(x),x=lc(x);
		Splay(x);
		return x;
	}
	void Link(int x,int y){
		MakeRoot(x);
		FindRoot(y);
		faz[x]=y;
		return ;
	}
	void Cut(int x,int y){
		MakeRoot(x);
		FindRoot(y);
		faz[y]=rc(x)=0;
		return ;
	}
	bool Query(int x,int y){
		return FindRoot(x)==FindRoot(y);
	}
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	while(m--){
		char opt[10];
		int x,y;
		cin>>opt>>x>>y;
		switch(opt[0]){
			case 'C':{
				LCT::Link(x,y);
				break;
			}case 'D':{
				LCT::Cut(x,y);
				break;
			}case 'Q':{
				if(LCT::Query(x,y))cout<<"Yes\n";
				else cout<<"No\n";
				break;
			}
		}
	}
	return 0;
}

维护边双连通分量

考虑当加入一条边的时候，如果形成了环，说明这些点一定在一个边双连通分量中，\(\text{Dfs}\) 这条链上的所有点，并通过并查集将其缩到一个点。相应的，\(\text{LCT}\) 的对应操作也需要通过并查集来跳转。

很显然这样的操作不支持删边。

【AHOI2005】航线规划

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

const int N=3e4+5,Q=4e4+5;

int n,m,tot;
int fa[N],ans[Q];
map<pii,bool>mp;
struct Query{
	int opt,l,r;
}q[Q];

int FindFaz(int x){
	if(fa[x]==x)return fa[x];
	return fa[x]=FindFaz(fa[x]);
}

void Merge(int x,int y){
	int a=FindFaz(x),b=FindFaz(y);
	if(a!=b)fa[a]=b;
	return ;
}

namespace LCT{
	#define faz(x) FindFaz(faz[x])
	#define lc(x) (ch[x][0])
	#define rc(x) (ch[x][1])
	#define get(x) (rc(faz(x))==x)
	int faz[N],ch[N][2],siz[N];
	bool tag[N];
	void Init(int x){
		lc(x)=rc(x)=0;
		siz[x]=1;
		return ;
	}
	bool IsRoot(int x){
		return lc(faz(x))==x||rc(faz(x))==x;
	}
	void PushUp(int x){
		siz[x]=siz[lc(x)]+siz[rc(x)]+1;
		return ;
	}
	void PushTag(int x){
		swap(lc(x),rc(x));
		tag[x]^=1;
		return ;
	}
	void PushDown(int x){
		if(tag[x]){
			if(lc(x))PushTag(lc(x));
			if(rc(x))PushTag(rc(x));
			tag[x]=0; 
		}
		return ;
	}
	void Rotate(int x){
		int y=faz(x),z=faz(y),k=get(x);
		if(IsRoot(y))ch[z][get(y)]=x;
		ch[y][k]=ch[x][!k],faz[ch[x][!k]]=y;
		ch[x][!k]=y,faz[y]=x,faz[x]=z;
		PushUp(y),PushUp(x);
		return ;
	}
	void Update(int x){
		if(IsRoot(x))Update(faz(x));
		PushDown(x);
		return ;
	}
	void Splay(int x){
		Update(x);
		for(int y;y=faz(x),IsRoot(x);Rotate(x)){
			if(IsRoot(y))Rotate(get(y)==get(x)?y:x);
		}
		return ;
	}
	void Access(int x){
		for(int y=0;x;x=faz(y=x)){
			Splay(x),rc(x)=y;
			PushUp(x);
		}
		return ;
	}
	void MakeRoot(int x){
		Access(x),Splay(x);
		PushTag(x);
		return ;
	}
	int FindRoot(int x){
		Access(x),Splay(x);
		while(lc(x))PushDown(x),x=lc(x);
		Splay(x);
		return x;
	}
	void Split(int x,int y){
		MakeRoot(x);
		Access(y),Splay(y);
		return ;
	}
	void Dfs(int x){
		PushDown(x);
		if(lc(x))Dfs(lc(x)),Merge(lc(x),x);
		if(rc(x))Dfs(rc(x)),Merge(rc(x),x);
		return ;
	}
	void Link(int x,int y){
		int a=FindFaz(x),b=FindFaz(y);
		if(FindRoot(a)==FindRoot(b)){
			Split(a,b);
			Dfs(b);
			int t=FindFaz(b);
			faz[t]=faz(b);
			Init(t);
		}else{
			MakeRoot(a);
			faz[a]=b;
		}
		return ;
	}
	int Query(int x,int y){
		int a=FindFaz(x),b=FindFaz(y);
		Split(a,b);
		return siz[b]-1;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		mp[{x,y}]=mp[{y,x}]=true;
	}
	while(1){
		int opt,x,y;
		cin>>opt;
		if(opt==-1)break;
		cin>>x>>y;
		q[++tot]={opt,x,y};
		if(opt==0)mp[{x,y}]=mp[{y,x}]=false;
	}
	for(auto it=mp.begin();it!=mp.end();it++){
		if(it->second){
			int x=it->first.first,y=it->first.second;
			mp[{x,y}]=mp[{y,x}]=false;
			LCT::Link(x,y);
		}
	}
	for(int i=tot;i>=1;i--){
		int x=q[i].l,y=q[i].r;
		if(q[i].opt==0)LCT::Link(x,y);
		else ans[i]=LCT::Query(x,y);
	}
	for(int i=1;i<=tot;i++){
		if(q[i].opt)cout<<ans[i]<<"\n";
	}
	return 0;
}

维护生成树

考虑一个最小生成树思路，对于一个环，我们显然可以考虑啊去掉里面边权最大的一条边，然后再添加新的边。由此，我们可以考虑维护链的最大值对应的编号。当我们需要删除某一个编号时，将其旋转到辅助树的根部，并将其和两个儿子的连接断开，这样就相当于删除了这一条边。

最小差值生成树

#include <bits/stdc++.h>
using namespace std;

const int N=5e4+5,M=2e5+5,W=1e4+5;

int n,m,ans,cnt;
bool book[M];
struct Edge{
	int u,v,w;
	friend bool operator <(Edge &a,Edge &b){return a.w<b.w;}
}e[M];
namespace LCT{
	#define lc(x) (ch[x][0])
	#define rc(x) (ch[x][1])
	#define get(x) (rc(faz[x])==x)
	int faz[N+M],ch[N+M][2],id[N+M],mn[N+M];
	bool tag[N+M];
	bool IsRoot(int x){
		return lc(faz[x])==x||rc(faz[x])==x;
	}
	void PushUp(int x){
		id[x]=x;
		if(id[lc(x)]>n&&(id[x]<=n||id[x]>id[lc(x)]))id[x]=id[lc(x)];
		if(id[rc(x)]>n&&(id[x]<=n||id[x]>id[rc(x)]))id[x]=id[rc(x)];
		return ;
	}
	void PushTag(int x){
		swap(lc(x),rc(x));
		tag[x]^=1;
		return ;
	}
	void PushDown(int x){
		if(tag[x]){
			if(lc(x))PushTag(lc(x));
			if(rc(x))PushTag(rc(x));
			tag[x]=0;
		}
		return ;
	}
	void Rotate(int x){
		int y=faz[x],z=faz[y],k=get(x);
		if(IsRoot(y))ch[z][get(y)]=x;
		ch[y][k]=ch[x][!k],faz[ch[x][!k]]=y;
		ch[x][!k]=y,faz[y]=x,faz[x]=z;
		PushUp(y),PushUp(x);
		return ;
	}
	void Update(int x){
		if(IsRoot(x))Update(faz[x]);
		PushDown(x);
		return ;
	}
	void Splay(int x){
		Update(x);
		for(int y;y=faz[x],IsRoot(x);Rotate(x)){
			if(IsRoot(y))Rotate(get(y)==get(x)?y:x);
		}
		return ;
	}
	void Access(int x){
		for(int y=0;x;x=faz[y=x]){
			Splay(x),rc(x)=y;
			PushUp(x);
		}
		return ;
	}
	void MakeRoot(int x){
		Access(x),Splay(x);
		PushTag(x);
		return ;
	}
	int FindRoot(int x){
		Access(x),Splay(x),PushDown(x);
		while(lc(x))PushDown(x=lc(x));
		Splay(x);
		return x;
	}
	void Split(int x,int y){
		MakeRoot(x);
		Access(y),Splay(y);
		return ;
	}
	bool Check(int x,int y){
		MakeRoot(x);
		return FindRoot(y)==x;
	}
	void Link(int x,int y){
		MakeRoot(x);
		faz[x]=y;
		return ;
	}
	void Query(int x,int y,int idx){
		if(Check(x,y)){
			Split(x,y);
			int pos=id[y];
			book[pos-n]=true;
			Splay(pos);
			faz[lc(pos)]=faz[rc(pos)]=0;
		}else cnt++;
		Link(x,idx);
		Link(idx,y);
		return ;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		e[i]={x,y,z};
	}
	sort(e+1,e+1+m);
	ans=W;
	int L=1;
	for(int i=1;i<=m;i++){
		int x=e[i].u,y=e[i].v;
		if(x==y){
			book[i]=true;
			continue ;
		}
		LCT::Query(x,y,n+i);
		while(book[L]&&L<=i)++L;
		if(cnt>=n-1)ans=min(ans,e[i].w-e[L].w);
	}
	cout<<ans;
	return 0;
}

标签：faz,LCT,return,lc,int,void,笔记,学习,rc
From： https://www.cnblogs.com/DycBlog/p/18518812

LCT 学习笔记