LCT学习笔记

这回是真的林克卡特树了（

简述

LCT 基于实链剖分，维护对象是一个森林。

对于一个节点，向某一个儿子的连边划分为实边，其他儿子的连边为虚边。虚实可以动态变化，所以要用 Splay 来维护每一条由若干实边连接成的实链。

LCT 支持以下操作：

• 查询、修改链信息
• 换根
• 动态加减边，合并/分离两棵树
• 动态维护连通性
• 其他

LCT 的主要性质：

• 每个 Splay 维护一条从上到下，按照在原树中的深度严格递增的路径，且中序遍历得到的深度序列严格递增。
• 每个节点属于且只属于一个 Splay 。
• 边分为实边和虚边，实边在 Splay 中，虚边由一棵 Splay 指向该 Splay 中序遍历最靠前的点在原树中的父亲。
• 由于性质2，当一个点有多个儿子时，显然只能连一条实边，而其他儿子不在这个 Splay 中，那么为了保持树的性质，其他儿子的边要成为虚边，由儿子所属 Splay 的根节点连向该点。

具体操作

其实就是几个基本操作拼来拼去啦QWQ 简单易上手的拼接玩具LCT，你值得拥有

access

操作目的：得到一个 Splay ，其中序遍历的起点是根，终点是指定点。

实现方式：

定义 ( ext{splay}(x)) 为将节点 (x) 转到当前 Splay 中的根。

循环进行如下步骤，直到操作点成为根节点：

1. 一次 ( ext{splay}) 将当前点转到根
2. 换儿子，将实边所指的儿子换到当前点
3. 更新信息
4. 当前点更换成虚边指向的父亲。（也就是当前 Splay 往上走）

void Access( int x ) 
{ 
	for ( int y=0; x; x=fa[y=x] ) 
		Splay(x),rc=y,Pushup(x); 
}

makeroot

操作目的：换根，让指定点成为原树的根。

实现方式：

注意到 ( ext{access}) 之后，当前点 (x) 在 Splay 中是深度最大的点；而 ( ext{splay}(x)) 之后，(x) 在 Splay 中没有右子树（因为性质一，不然不能保证中序遍历深度的严格递增）。所以翻转整个 Splay （也就是交换左右子树，打标记）之后，(x) 就会成为深度最小的点（根节点）。

void MakeRoot( int x ) 
{ 
	Access(x); Splay(x); Flip(x); 
} 

findroot

操作目的：找到 (x) 所在原树的树根，主要用来判定连通性。

实现方式：

根据性质一，我们只需要不断走一个点的左儿子，深度是单调递减的。所以先 ( ext{access}) 一下，然后 ( ext{splay}) 一遍转到根，不断往左子树走就好了。最后把得到的 (x) 给 ( ext{splay}) 上去即可。

int FindRoot( int x )		//找原树上的树根
{
	Access(x); Splay(x);			//取出路径，转到根
	while ( lc ) Pushdown( x ),x=lc;		//每次往深度小的左子树走
	Splay(x); return x;	
}

split

操作目的：拉出 (x o y) 的路径，使之成为一个 Splay （不妨设最后的根是 (y) ）.

实现方式：先 ( ext{makeroot}) 让 (x) 成为根，然后对 (y) 进行 ( ext{access}) ，这样就拿出了这条路径，最后为了让 (y) 成为根，( ext{splay}(y)) 即可。

void Split( int x,int y ) 
{ 
	MakeRoot(x); Access(y); Splay(y); 
}	//取出路径

link

操作目的：加一条 ((x,y)) 的边。（这里是让 (x) 的父亲指向 (y) ，连一条轻边）

实现方式：先 ( ext{makeroot}(x)) ，然后令 (f[x]=y) 即可。

注意，如果题目没有保证连边一定合法，要先判一遍 (x,y) 的连通性。

void Link( int x,int y ) 
{ 
	MakeRoot(x); 
	if ( FindRoot(y)^x ) fa[x]=y; 
} //加边

cut

操作目的：将边 ((x,y)) 断开。

如果保证合法显然不难：

先搞一个 ( ext{split}) 拿出 ((x,y)) ，然后直接断掉 (y) 的左儿子，断掉 (x) 的父亲即可。最后不要忘记 ( ext{pushup}) .

如果不一定存在呢？

首先 ( ext{makeroot}(x)) ，然后用 ( ext{findroot}(y)) 判断连通性。接下来再判断 (x,y) 是否有父子关系，和 (y) 是否有左儿子（因为如果没有直接连边，中序遍历中左儿子会在 (x,y) 之间）。判断完之后就断掉 (x) 的右子树和 (y) 的父亲即可。最后还是要 ( ext{pushup}(x)) .

void Cut( int x,int y ) 	//删边
{
	MakeRoot(x);	//分别判连通性，父子关系，左儿子
	if ( FindRoot(y)==x && fa[y]==x && !tr[y][0] ) 
	{ 
		fa[y]=tr[x][1]=0; Pushup(x); 
	}
}

模板

题目链接

维护四种操作：加边，删边，查询路径异或和，单点改点权。

代码略有压行（

//Author:RingweEH
//P3690 【模板】Link Cut Tree
#define lc tr[x][0]
#define rc tr[x][1]
const int N=3e5+10;
int fa[N],tr[N][2],val[N],sum[N],n,m,sta[N];
bool tag[N];

bool IsRoot( int x ) { return (tr[fa[x]][0]==x) || (tr[fa[x]][1]==x); }	
//判断Splay的根，如果是虚边显然不会是父亲的儿子
void Pushup( int x ) { sum[x]=sum[lc]^sum[rc]^val[x]; }
void Flip( int x ) { int tmp=lc; lc=rc; rc=tmp; tag[x]^=1; } //Splay翻转
void Pushdown( int x )		//标记下传，默认自己已经翻转完了
{
	if ( tag[x] )
	{
		if ( lc ) Flip( lc );
		if ( rc ) Flip( rc );
		tag[x]=0;
	}
}
void Rotate( int x )
{
	int y=fa[x],z=fa[y],kid=tr[y][1]==x,oth=tr[x][!kid];
	if ( IsRoot(y) ) tr[z][tr[z][1]==y]=x;
	tr[x][!kid]=y; tr[y][kid]=oth;
	if ( oth ) fa[oth]=y;
	fa[y]=x; fa[x]=z; Pushup(y);
}
void Splay( int x )
{
	int y=x,top=0; sta[++top]=y;
	while ( IsRoot(y) ) sta[++top]=y=fa[y];
	while ( top ) Pushdown(sta[top--]);
	while ( IsRoot(x) )
	{
		y=fa[x]; top=fa[y];
		if ( IsRoot(y) ) Rotate((tr[y][0]==x)^(tr[top][0]==y) ? x : y );
		Rotate(x);
	}
	Pushup(x);
}
void Access( int x ) { for ( int y=0; x; x=fa[y=x] ) Splay(x),rc=y,Pushup(x); } //取到根
void MakeRoot( int x ) { Access(x); Splay(x); Flip(x); }	//换根 
int FindRoot( int x )		//找原树上的树根
{
	Access(x); Splay(x);			//取出路径，转到根
	while ( lc ) Pushdown( x ),x=lc;		//每次往深度小的左子树走
	Splay(x); return x;	
}
void Split( int x,int y ) { MakeRoot(x); Access(y); Splay(y); }	//取出路径
void Link( int x,int y ) { MakeRoot(x); if ( FindRoot(y)^x ) fa[x]=y; } //加边
void Cut( int x,int y ) 	//删边
{
	MakeRoot(x);	//分别判连通性，父子关系，左儿子
	if ( FindRoot(y)==x && fa[y]==x && !tr[y][0] ) { fa[y]=tr[x][1]=0; Pushup(x); }
}

int main()
{
	n=read(); m=read();
	for ( int i=1; i<=n; i++ ) val[i]=read();
	while ( m-- )
	{
		int opt=read(),x=read(),y=read();
		if ( opt==0 ) Split( x,y ),printf("%d
",sum[y] );
		else if ( opt==1 ) Link(x,y);
		else if ( opt==2 ) Cut(x,y);
		else if ( opt==3 ) Splay(x),val[x]=y;
	}

	return 0;
}

应用：维护链上信息

举个例子？模板就是。

弹飞绵羊

有 (n) 个带点权的点，在走到第 (i) 个点时会跳到第 (i+k_i) 个，如果不存在那么就飞了。

维护单点修改，查询从第 (i) 个点开始几次会飞。

---

建图一眼题。显然是 ((i,i+k_i)) 连边，这里有两种写法：

第一种，把飞的情况视为终点，那么就是一棵树，原封不动套板子就行。

第二种，把飞的边忽略掉，那么查询步数就是查询点到原树根节点的路径长度。发现我们根本不需要换根这个操作，那么就可以对板子进行一些魔改：

• 对于连边，由于是一棵树，所以直接改父亲，连轻边。
• 对于删边，用 ( ext{access}) ，( ext{splay}) 来确定父亲位置，这时候父亲一定在左子树中，直接双向断开即可。
• 对于查询，直接 ( ext{access}) 然后 ( ext{splay}) ，输出 (siz) 即可。

这里是第二种的参考代码。

//Author:RingweEH
//P3203 [HNOI2010]弹飞绵羊
bool IsRoot( int x ) { return (tr[fa[x]][0]==x) || (tr[fa[x]][1]==x); } 
void Pushup( int x ) { sum[x]=sum[lc]+sum[rc]+1; }
void Rotate( int x )
{
    int y=fa[x],z=fa[y],kid=tr[y][1]==x,oth=tr[x][!kid];
    if ( IsRoot(y) ) tr[z][tr[z][1]==y]=x;
    tr[x][!kid]=y; tr[y][kid]=oth;
    if ( oth ) fa[oth]=y;
    fa[y]=x; fa[x]=z; Pushup(y);
}
void Splay( int x )
{
    int y,z;
    while ( IsRoot(x) )
    {
        y=fa[x]; z=fa[y];
        if ( IsRoot(y) ) Rotate((tr[y][0]==x)^(tr[z][0]==y) ? x : y );
        Rotate(x);
    }
    Pushup(x);
}
void Access( int x ) { for ( int y=0; x; x=fa[y=x] ) Splay(x),rc=y,Pushup(x); }

int main()
{
    n=read(); 
    for ( int i=1,k; i<=n; i++ )
    {
        sum[i]=1; k=read();
        if ( i+k<=n ) fa[i]=i+k;
    }
    m=read();
    while ( m-- )
    {
        int opt=read(),x=read(),y;		//注意标号从0开始
        if ( opt&1 ) { x++; Access(x); Splay(x); printf( "%d
",sum[x] ); }
        else
        {
            x++; y=read(); Access(x); Splay(x);
            tr[x][0]=fa[tr[x][0]]=0;		//直接双向断边
            if ( x+y<=n ) fa[x]=x+y; 		//加新边
            Pushup(x);
        }
    }

    return 0;
}

应用：维护连通性

如果只是维护连通性，直接 ( ext{findroot}) 就好了。

不过 sk 的首页写着 我单方面宣布 findroot × ？不太懂，可能是复杂度出了什么大问题，下次问问他

upd：好像 ( ext{findroot}) 复杂度确实不行……能用并查集尽量并查集吧.

如果要维护双连通分量，就套个并查集，然后加边时如果不连通就合并，如果联通就说明有环，缩点合并即可。

部落冲突

维护一棵树，支持加边，删边，询问连通性。

---

无脑 LCT 好啊。注意，题目虽然保证了一打东西，但是 ( ext{Cut}) 还是要特判，不然会五颜六色……

上次交这道题是在去年暑假了，开 O2 就 1.44s ，但是这次没开就直接 1.36s 了，开完之后直接 927ms 了 /cy .

#define PII pair<int,int>
PII event[N];

int main()
{
    n=read(); m=read(); int u,v,tot=0;
    for ( int i=1; i<n; i++ ) u=read(),v=read(),Link(u,v);

    while ( m-- )
    {
        char opt[5]; scanf( "%s",opt );
        if ( opt[0]=='Q') u=read(),v=read(),MakeRoot(u),puts( (u^FindRoot(v)) ? "No" : "Yes" );
        else if ( opt[0]=='C' ) u=read(),v=read(),event[++tot]=make_pair(u,v),Cut(u,v);
        else u=read(),Link( event[u].first,event[u].second ); 
    }
}

应用：维护链上的边权信息

两个字：拆边 。

把边看做一个点，向两个端点连边。由于不需要维护真正的点权，所以代表点的点权设空。写的时候直接 ( ext{link/cut}) 两次就好了。

最小差值生成树

求边权最大值与最小值的差值最小的生成树。

---

从小到大对边权排序，每次枚举一条边，没连通就连上，否则就替换环上最小的一条边，有了生成树之后每次更新答案。

维护最小边就直接搞个指针就好了。不知道为什么这份代码松得不行……随手一交就最优解 rank3 了虽然开O2一点用都没有 。

我学习的博客的那个博主开了 fread + O2 松不过我一个快读不开 O2 的大常数老年选手（

//Author:RingweEH
#define lc tr[x][0]
#define rc tr[x][1]
const int N=5e4+10,M=2e5+10,P=N+M,INF=0x3f3f3f3f;
int f[P],tr[P][2],mn[P],fa[N],val[P],n,m,ans;
bool tag[P],vis[M];
struct Edge
{
    int fro,to,len;
    bool operator < ( Edge tmp ) { return len<tmp.len; }
}e[M];
bool IsRoot( int x ) { return tr[f[x]][0]==x || tr[f[x]][1]==x; }
int vmin( int x,int y ) { return val[x]<val[y] ? x : y; }
void Pushup( int x ) { mn[x]=vmin(x,vmin(mn[lc],mn[rc])); }
void Pushdown( int x ) { if ( tag[x] ) { int tmp=lc; tag[lc=rc]^=1; tag[rc=tmp]^=1; tag[x]=0; } }
void Pushall( int x ) { if ( IsRoot(x) ) Pushall(f[x]); Pushdown(x); }
void Rotate( int x ) 
{
    int y=f[x],z=f[y],kid=tr[y][1]==x,oth=tr[x][!kid];
    if ( IsRoot(y) ) tr[z][tr[z][1]==y]=x;
    tr[x][!kid]=y; tr[y][kid]=oth; f[oth]=y; f[y]=x; f[x]=z;
    Pushup(y);
}
void Splay( int x )
{
    int y=x; Pushall(x);
    while ( IsRoot(x) )
    {
        if ( IsRoot(y=f[x]) ) Rotate( (tr[y][0]==x)^(tr[f[y]][0]==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); tag[x]^=1; }
void Link( int i ) { MakeRoot(e[i].fro); f[f[e[i].fro]=N+i]=e[i].to; }
void Cut( int x ) { Access(e[x-N].fro); Splay(x); lc=rc=f[lc]=f[rc]=0; }
int Find( int x ) { return x==fa[x] ? x : fa[x]=Find(fa[x]); }

int main()
{
    n=read(); m=read();
    for ( int i=0; i<=n; i++ ) fa[i]=i,val[i]=INF;
    for ( int i=1; i<=m; i++ ) e[i].fro=read(),e[i].to=read(),e[i].len=read();

    sort( e+1,e+1+m ); int cnt=1,pt=1,x,y;
    for ( int i=1; i<=m; i++ )
    {
        val[i+N]=e[i].len;
        if ( Find(x=e[i].fro)^Find(y=e[i].to) )
        {
            vis[i]=1; Link(i); fa[fa[x]]=fa[y]; cnt++;
            if ( cnt==n ) ans=e[i].len-e[pt].len;
        }
        else
        {
            if ( x==y ) continue;
            vis[i]=1; MakeRoot(x); Access(y); Splay(y); vis[mn[y]-N]=0; 
            while ( !vis[pt] ) pt++;
            Cut(mn[y]); Link(i);
            if ( cnt==n ) bmin( ans,e[i].len-e[pt].len );
        }
    }
    printf( "%d
",ans );
    return 0;
}

应用：维护虚子树信息总和与原树信息总和

由于原树的边只有实边和虚边两种，所以子树也可以分成实子树和虚子树，而实子树可以通过 Splay 得到（显然实子树就是一条实链），那么我们需要维护的就是虚子树和，总和可以通过这两个东西得到。

下面用 (si) 表示虚子树信息和，用 (s) 表示原树信息和。

显然 (s) 就是实加虚，所以不难得出 ( ext{pushup}) 的代码：

void Pushup( int x ) { s[x]=s[lc]+s[rc]+si[x]+v[x]; }

然后来考虑每个操作对虚实边的影响。

( ext{access}) ：每一次 ( ext{splay}) 之后，更改了右子树，得到了一个虚儿子，失去了一个，总和没变。那么就直接让 (si) 加上原来右儿子的 (s) ，再减去新的右儿子的 (s) 即可。（如果 ( ext{pushup}) 只维护 (s) 可以直接删去）

void Access( int x )
{
	for ( int y=0; x; x=f[y=x] )
	{
		Splay(x);
		si[x]+=s[c[x][1]]; si[x]-=s[c[x][1]=y];
		pushup(x);
	}
}

( ext{link}) ：(y) 多了一个虚边指向儿子 (x) ，那么 (s[y],si[y]+=s[x]) ，而且 (y) 在 LCT 中的祖先的 (x) 同样要累加，所以一开始要把 (y) 转到根。

//保证合法
void Link( int x,int y )
{
	Split( x,y ); si[fa[x]=y]+=s[x]; Pushup(y);
}
//不保证
bool Link( int x,int y ) 
{
	MakeRoot( x );
	if ( FindRoot(y)==x ) return 0;
	si[fa[x]=y]+=s[x]; Pushup(y); return 1;
}

大融合

构建一棵树，在加边过程中动态查询经过某条边的路径数量。

---

仔细想想就会发现，路径数就是 ( ext{split}(x,y)) 之后两棵虚子树 (siz+1) 的乘积。直接上板子就好了。

//Author:RingweEH
//P4219 [BJOI2014]大融合
#define lc tr[x][0]
#define rc tr[x][1]
const int N=1e5+10;
int fa[N],tr[N][2],s[N],si[N],n,m;
bool tag[N];
bool IsRoot( int x ) { return (tr[fa[x]][0]==x) || (tr[fa[x]][1]==x); }	
void Pushup( int x ) { s[x]=s[lc]+s[rc]+si[x]+1; }
void Pushdown( int x )	{ if ( tag[x] ) { int tmp=lc; lc=rc; rc=tmp; tag[lc]^=1; tag[rc]^=1; tag[x]=0; } }
void Pushall( int x ) { if ( IsRoot(x) ) Pushall(fa[x]); Pushdown(x); }
void Rotate( int x ) 
{
    int y=fa[x],z=fa[y],kid=tr[y][1]==x,oth=tr[x][!kid];
    if ( IsRoot(y) ) tr[z][tr[z][1]==y]=x;
    tr[x][!kid]=y; tr[y][kid]=oth; fa[oth]=y; fa[y]=x; fa[x]=z;
    Pushup(y);
}
void Splay( int x )
{
    int y=x; Pushall(x);
    while ( IsRoot(x) )
    {
        if ( IsRoot(y=fa[x]) ) Rotate( (tr[y][0]==x)^(tr[fa[y]][0]==y) ? x : y );
        Rotate(x);
    }
    Pushup(x);
}
void Access( int x ) { for ( int y=0; x; x=fa[y=x] ) Splay(x),si[x]+=s[rc],si[x]-=s[rc=y]; } 
void MakeRoot( int x ) { Access(x); Splay(x); tag[x]^=1; }	 
void Split( int x,int y ) { MakeRoot(x); Access(y); Splay(y); }	
void Link( int x,int y ) { Split(x,y); si[fa[x]=y]+=s[x]; Pushup(y); } 

int main()
{
	n=read(); m=read();
	for ( int i=1; i<=n; i++ ) s[i]=1;
	while ( m-- )
	{
		char opt[5]; scanf( "%s",opt ); int x=read(),y=read();
		if ( opt[0]=='A' ) Link(x,y);
		else Split(x,y),printf("%lld
",1ll*(si[x]+1)*(si[y]+1) );
	}

	return 0;
}

学习博客

Flash_Hu ：概念篇 应用篇

想要更多习题也可以看这里QWQ