Link-Cut Tree

发表于 | 分类于 | 阅读次数:

由于本文涉及的许多专有名词并没有统一的中文译名，所以本文译名与其他资料不尽相同，尽请谅解。
##概念

动态树问题, 即要求我们维护一个由若干棵子结点无序的有根树组成的森林. 要求这个数据结构支持对树的分割, 合并, 对某个点到它的根的路径的某些操作, 以及对某个点的子树进行的某些操作.

Link-Cut Tree, LCT 是一种能快速解决动态树问题的数据结构。

如果刚刚执行了对这个节点的 access 操作，那么我们称这个点刚刚被访问过。如果在一个节点 u 的子树中， v 刚刚被访问过，那么称 v 是 u 的偏爱子节点 ( Preferred Child ) ；每个点到它的偏爱子节点的边叫偏爱边 ( Preferred Edge ) ；由偏爱边所连接成的最长链则称为偏爱路径 ( Preferred Path ) 。

我们把整棵树划分为若干条偏爱路径后，我们用伸展树来维护这些路径，对于每条路径建一个伸展树，伸展树以每个点在原树中的深度为关键字，也就是说，在一棵伸展树中，一个节点的左子树的节点在原树中比它的深度小，右子树的节点在原树中比它的深度大。我们称这样得到的伸展树森林中的一棵伸展树为辅助树 ( Auxiliary Tree ) ，意为用于辅助维护原树中的偏爱路径的树。

知道了组成原树的路径后，只需知道这些路径之间的关系就可以表示出原树了。我们称原树中某一偏爱路径的辅助树的根节点的父亲为此路径的路径父亲 ( Path Parent ) ，而原树的根节点所在的偏爱路径的路径父亲未定义。

##操作
实际上我们将路径父节点和节点的父节点都使用一个数组表示的，而唯一能区分的地方就是一个节点的父亲的儿子并不是它， 我们需要利用这点区分每个平衡树，并在伸展时注意不要改变所在平衡树外的形态。
###Access(x)
Access 操作是 LCT 各种操作的基础，它的作用是访问一个节点，根据概念中所规定的，我们需要将此节点到其所在树的根节点路径化为偏爱路径，并将此节点与其偏爱儿子间的偏爱边变为非偏爱边。

实现方式是将 x 节点到根的每一个节点遍历一遍，记录节点 x 是从 y 节点上来的。每次在辅助树中将 x 伸展到根节点，然后将 y 连到 x 的右子树上，这样也可以保证最开始的 x 点的下面的偏爱路径被清除。

###MakeRoot(x)
MakeRoot 操作的作用就是把 x 节点变为原树的根，这是唯一一个对原树有影响的操作，不过也只是更改了一下根，并没有改变形态。

方法： access(x), splay(x), 翻转 x 所在平衡树
###FindRoot(x)
方法： access(x),splay(x), 最左边的节点就是根
###Link(x, y)
作用：把 y 的路径父亲设为 x ，当然，由于只有路径的平衡树根有路径父亲，所以首先要保证 y 是根节点；

方法：splay(y), fa[y]=x;
###Split(x, y)
此函数并无应用性，只是为之后的其他操作做准备。
作用是将 x 和 y 之间的路径连接起来，并使 y 成为所在辅助树的根，方便以后操作。
###Cut(x, y)
在分离的时候直接把父亲、儿子赋为 0 即可，唯一需要注意的是应判断两节点是否在一棵树上。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
const int MAXN=3e5+5,INF=~0U>>1;
int n,m;
struct N
{
	int val,c[2],fa,sum,mx,det,sz;bool rev;
} t[MAXN];
int q[MAXN],tp;
void add(int x,int v)
{t[x].val+=v;t[x].sum+=v*t[x].sz;t[x].mx+=v;t[x].det+=v;}
void upd(int x)
{
	int lc=t[x].c[0],rc=t[x].c[1];
	t[x].sum=t[lc].sum+t[rc].sum+t[x].val;
	t[x].sz=t[lc].sz+t[rc].sz+1;
	t[x].mx=std::max(std::max(t[lc].mx,t[rc].mx),t[x].val);
}
void pushdown(int x)
{
	if(t[x].rev){t[t[x].c[0]].rev^=1;t[t[x].c[1]].rev^=1;t[x].rev^=1;swap(t[x].c[0],t[x].c[1]);}
	if(t[x].det) add(t[x].c[0],t[x].det),add(t[x].c[1],t[x].det),t[x].det=0;
}

inline bool isRt(int x){return t[t[x].fa].c[0]!=x&&t[t[x].fa].c[1]!=x;}
inline bool iden(int x){return t[t[x].fa].c[1]==x;}
void rot(int x)
{
	int y=t[x].fa,z=t[y].fa;
	pushdown(y);pushdown(x);
	bool xT=iden(x),yT=iden(y);
	if(!isRt(y)) t[z].c[yT]=x;
	t[x].fa=z;t[y].fa=x;t[t[x].c[!xT]].fa=y;
	t[y].c[xT]=t[x].c[!xT];t[x].c[!xT]=y;
	upd(y);upd(x);
}
void splay(int x)
{
	pushdown(x);
	while(!isRt(x))
	{
		int y=t[x].fa,z=t[y].fa;
		if(!isRt(y))
		{
			if(iden(x)^iden(y)) rot(x);
			else rot(y);
		} rot(x);
	}
}
void access(int x){for(int y=0;x;y=x,x=t[x].fa) splay(x),t[x].c[1]=y,upd(x);}
  
int findRt(int x){access(x);splay(x);while(t[x].c[0]) x=t[x].c[0];return x;}
  
void makeRt(int x){access(x);splay(x);t[x].rev^=1;}
  
void split(int x,int y){makeRt(x);access(y);splay(y);}
 
void cut(int x,int y){split(x,y);t[y].c[0]=t[x].fa=0;}
  
void link(int x,int y){makeRt(y);t[y].fa=x;}

##使用方法
一些显而易见的使用方法就不再赘述了，主要说一下两种：

  • 更改点权：为方便更新，我们先 splay 再更改 splay(x),t[x].val=y,upd(x);

  • 各种 (x, y) 路径上的区间操作：先 split 再操作

    1
    2
    3
    4
    5
    6
    7
    if(opt==1) link(x,y);
    else if(opt==2) cut(x,y);
    else if(opt==3) splay(x),t[x].val=y,upd(x);
    else if(opt==4) split(x,y),printf("%d\n",t[y].mx);
    else if(opt==5) split(x,y),printf("%d\n",t[y].sum);
    else if(opt==6) printf("%d\n",findRt(x)==findRt(y));
    else if(opt==7) split(x,y),add(y,read());

##应用&题目
###[BZOJ3282] Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=3e5+5;
int n,m;
struct LCT
{
    struct N
    {
        int val,c[2],fa,xr,rev;
    } t[MAXN];
    int q[MAXN],tp;
    inline void upd(int x){t[x].xr=t[t[x].c[0]].xr^t[t[x].c[1]].xr^t[x].val;}
    inline void pushdown(int x)
    {if(t[x].rev){t[t[x].c[0]].rev^=1;t[t[x].c[1]].rev^=1;t[x].rev^=1;swap(t[x].c[0],t[x].c[1]);}}

    inline bool isRt(int x){return t[t[x].fa].c[0]!=x&&t[t[x].fa].c[1]!=x;}
    inline bool iden(int x){return t[t[x].fa].c[1]==x;}
    void rot(int x)
    {
        int y=t[x].fa,z=t[y].fa;
        pushdown(y);pushdown(x);
        bool xT=iden(x),yT=iden(y);
        if(!isRt(y)) t[z].c[yT]=x;
        t[x].fa=z;t[y].fa=x;t[t[x].c[!xT]].fa=y;
        t[y].c[xT]=t[x].c[!xT];t[x].c[!xT]=y;
        upd(y);upd(x);
    }
    void splay(int x)
    {
        pushdown(x);
        while(!isRt(x))
        {
            int y=t[x].fa,z=t[y].fa;
            if(!isRt(y))
            {
                if(iden(x)^iden(y)) rot(x);
                else rot(y);
            } rot(x);
        }
    }
    void access(int x){for(int y=0;x;y=x,x=t[x].fa) splay(x),t[x].c[1]=y,upd(x);}

    int findRt(int x){access(x);splay(x);while(t[x].c[0]) x=t[x].c[0];return x;}

    void makeRt(int x){access(x);splay(x);t[x].rev^=1;}

    void split(int x,int y){makeRt(x);access(y);splay(y);}

    void cut(int x,int y){split(x,y);t[y].c[0]=t[x].fa=0;}

    void link(int x,int y){makeRt(y);t[y].fa=x;}
} lct;

inline int read()
{
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) lct.t[i].xr=lct.t[i].val=read();
    while(m--)
    {
        int opt=read(),x=read(),y=read();
        if(opt==0){lct.split(x,y);printf("%d\n",lct.t[y].xr);}
        else if(opt==1){if(lct.findRt(x)!=lct.findRt(y)) lct.link(x,y);}
        else if(opt==2){if(lct.findRt(x)==lct.findRt(y)) lct.cut(x,y);}
        else if(opt==3){lct.access(x);lct.splay(x);lct.t[x].val=y;lct.upd(x);}
    }
    return 0;
}

###[COGS2701] 动态树
这道题还有点价值。题目要求求子树大小，单是平衡树的话，子树大小还是很好算的，所以我们只需再统计一下非偏爱子树（即虚子树）大小即可。

我们这里对每个节点用 vir 记录其虚子树大小，注意在 splay, access, link 过程中更新即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
const int MAXN=2e5+5,INF=~0U>>1;
int n,m;
struct N
{
	int val,c[2],fa,sum,mx,det,sz,vir;bool rev;
} t[MAXN];
void upd(int x)
{t[x].sz=t[t[x].c[0]].sz+t[t[x].c[1]].sz+t[x].vir+1;}
void pushdown(int x)
{if(t[x].rev){t[t[x].c[0]].rev^=1;t[t[x].c[1]].rev^=1;t[x].rev^=1;std::swap(t[x].c[0],t[x].c[1]);}}

inline bool isRt(int x){return t[t[x].fa].c[0]!=x&&t[t[x].fa].c[1]!=x;}
inline bool iden(int x){return t[t[x].fa].c[1]==x;}
void rot(int x)
{
	int y=t[x].fa,z=t[y].fa;
	pushdown(y);pushdown(x);
	bool xT=iden(x),yT=iden(y);
	if(!isRt(y)) t[z].c[yT]=x;t[x].fa=z;
	t[y].fa=x;t[t[x].c[!xT]].fa=y;
	t[y].c[xT]=t[x].c[!xT];t[x].c[!xT]=y;
	upd(y);upd(x);
}
void splay(int x)
{
	pushdown(x);
	while(!isRt(x))
	{
		int y=t[x].fa,z=t[y].fa;
		if(!isRt(y))
		{
			if(iden(x)^iden(y)) rot(x);
			else rot(y);
		} rot(x);
	}
}
void access(int x)
{
	for(int y=0;x;y=x,x=t[x].fa) 
	{
		splay(x);
		t[x].vir-=t[y].sz;
		t[x].vir+=t[t[x].c[1]].sz;
		t[x].c[1]=y;
		upd(x);
	}
}
void makeRt(int x){access(x);splay(x);t[x].rev^=1;}

int findRt(int x){access(x);splay(x);while(t[x].c[0]) x=t[x].c[0];return x;}

void link(int x,int y){makeRt(y);t[y].fa=x;t[x].vir+=t[y].sz;}


int read()
{
	int flag=1,x=0;char ch;
	do{ch=getchar();if(ch=='-')flag=-1;}while(ch<'0'||ch>'9');
	do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
	return flag*x;
}
int main()
{
	freopen("dynamic_tree.in","r",stdin);
	freopen("dynamic_tree.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++) t[i].sz=1;
	while(m--)
	{
		int opt=read(),u=read();
		if(opt==1) makeRt(u);
		else if(opt==2) access(u),printf("%d\n",t[u].vir+1);
		else if(opt==3) 
		{int uRt=findRt(u);link(u,read());makeRt(uRt);}
	}
	return 0;
}

[BZOJ2049][Sdoi2008] Cave 洞穴勘测

开始时有 $n$ 个孤立点，之后进行 $m$ 次操作，将两个点之间连边或删边，或询问两点之间的连通性。

$n\leq10^4,m\leq2\times10^5$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**************************************************************
    Problem: 2049
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:1696 ms
    Memory:1488 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
 
const int MAXN=1e4+5;
int n,m;
struct N{int val,c[2],fa;bool rev;} t[MAXN];
 
void pushdown(int x)
{
    if(t[x].rev)
    {
        t[t[x].c[0]].rev^=1;t[t[x].c[1]].rev^=1;
        t[x].rev^=1;std::swap(t[x].c[0],t[x].c[1]);
    }
}
 
inline bool isRt(int x){return t[t[x].fa].c[0]!=x&&t[t[x].fa].c[1]!=x;}
inline bool iden(int x){return t[t[x].fa].c[1]==x;}
void rot(int x)
{
    int y=t[x].fa,z=t[y].fa;
    pushdown(y);pushdown(x);
    bool xT=iden(x),yT=iden(y);
    if(!isRt(y)) t[z].c[yT]=x;
    t[x].fa=z;t[y].fa=x;t[t[x].c[!xT]].fa=y;
    t[y].c[xT]=t[x].c[!xT];t[x].c[!xT]=y;
}
void splay(int x)
{
    pushdown(x);
    while(!isRt(x))
    {
        int y=t[x].fa,z=t[y].fa;
        if(!isRt(y))
        {
            if(iden(x)^iden(y)) rot(x);
            else rot(y);
        } rot(x);
    }
}
 
void access(int x){for(int y=0;x;y=x,x=t[x].fa) splay(x),t[x].c[1]=y;}
 
int findRt(int x){access(x);splay(x);while(t[x].c[0]) x=t[x].c[0];return x;}
 
void makeRt(int x){access(x);splay(x);t[x].rev^=1;}
 
void split(int x,int y){makeRt(x);access(y);splay(y);}
 
void cut(int x,int y){split(x,y);t[y].c[0]=t[x].fa=0;}
 
void link(int x,int y){makeRt(y);t[y].fa=x;}
 
int main()
{
    int i;
    char opt[10];int x,y;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%s%d%d",opt,&x,&y);
        if(opt[0]=='C') link(x,y);
        else if(opt[0]=='D') cut(x,y);
        else
        {
            if(findRt(x)==findRt(y)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

[Hnoi2010] Bounce 弹飞绵羊

地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$ ，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$ 个装置，若不存在第 $i+k_i$ 个装置，则绵羊被弹飞。绵羊想知道当它从第 $i$ 个装置起步时，被弹几次后会被弹飞。可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

$n\leq2\times10^5,m\leq10^5$

这道题其实有神奇的分块做法，考虑用动态树做法的话，因为所有被弹飞的绵羊一定要到达 $i+k_i$ 的一个不存在的装置，只要新建一个根，代表绵羊被弹飞的状态，那么就可以用 Link-Cut Tree 的做法来解决此问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/**************************************************************
    Problem: 2002
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:2192 ms
    Memory:6760 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
  
const int MAXN=2e5+5;
 
int n,m;
 
int k[MAXN];
 
struct N
{
    int val,c[2],fa,sz;bool rev;
} t[MAXN];
 
void upd(int x){t[x].sz=t[t[x].c[0]].sz+t[t[x].c[1]].sz+1;}
 
void pushdown(int x)
{
    if(t[x].rev)
    {
        t[t[x].c[0]].rev^=1;t[t[x].c[1]].rev^=1;
        t[x].rev^=1;std::swap(t[x].c[0],t[x].c[1]);
    }
}
  
inline bool isRt(int x){return t[t[x].fa].c[0]!=x&&t[t[x].fa].c[1]!=x;}
inline bool iden(int x){return t[t[x].fa].c[1]==x;}
void rot(int x)
{
    int y=t[x].fa,z=t[y].fa;
    pushdown(y);pushdown(x);
    bool xT=iden(x),yT=iden(y);
    if(!isRt(y)) t[z].c[yT]=x;
    t[x].fa=z;t[y].fa=x;t[t[x].c[!xT]].fa=y;
    t[y].c[xT]=t[x].c[!xT];t[x].c[!xT]=y;
    upd(y);upd(x);
}
void splay(int x)
{
    pushdown(x);
    while(!isRt(x))
    {
        int y=t[x].fa,z=t[y].fa;
        if(!isRt(y))
        {
            if(iden(x)^iden(y)) rot(x);
            else rot(y);
        } rot(x);
    }
}
  
void access(int x){for(int y=0;x;y=x,x=t[x].fa) splay(x),t[x].c[1]=y,upd(x);}
  
int findRt(int x){access(x);splay(x);while(t[x].c[0]) x=t[x].c[0];return x;}
  
void makeRt(int x){access(x);splay(x);t[x].rev^=1;}
  
void split(int x,int y){makeRt(x);access(y);splay(y);}
 
void cut(int x,int y){split(x,y);t[y].c[0]=t[x].fa=0;}
  
void link(int x,int y){makeRt(y);t[y].fa=x;}
  
int main()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n+1;i++) t[i].sz=1;
    for(i=1;i<=n;i++)
    {
        scanf("%d",k+i);
        if(k[i]+i>n) k[i]=n+1-i;
        link(i+k[i],i);
    }
    scanf("%d",&m);
    while(m--)
    {
        int opt,x,v;
        scanf("%d%d",&opt,&x);x++;
        if(opt==1)
        {
            makeRt(n+1);
            makeRt(x);
            printf("%d\n",t[x].sz-1);
        }else
        {
            scanf("%d",&v);
            cut(x+k[x],x);
            k[x]=v;
            if(k[x]+x>n) k[x]=n+1-x;
            link(x+k[x],x);
        }
    }
    return 0;
}