学一下LCT，有多道例题

acm LCT
算法学习
发布日期:   2022-08-25
文章字数:   2.2k

LCT(link-cut tree)

前言

关于我为什么要学这个东西

学这个是因为我要学习这道题的写法，而这道题是用到了 $LCT$ ，于是，学一下。

大概解释

这里不做详细解释，只粗略的做个描述。

$LCT$ 和树链剖分很像，但是， $LCT$ 并不是根据轻重链来分的，而是根据需要，可以随意的分。

$LCT$ 在结构上看，整体结构就是”树链剖分+ $splay$ “，这里面，每条独立的链的内部都是一个 $splay$ 来进行维护的。里面的各种函数都是在这个基础上进行操作的。

我的重点不在此处，这里不做过多解释，便只描述了一下整体结构。

适用场景

学了一下才发现，这东西是真的妙啊，这个东西是个动态树。

可以支持动态维护一个树结构，具体来说就是支持加边和删除边。

可以用来求无根树的lca，就是可以多次随意指定一个根来求lca。

这个东西还可以当作一个动态并查集来使用。即可以加边也可以删边的并查集。

几个例题

题目传送门

代码

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;

struct LCT{
    struct node{
        int fa,left,right,val,sum,lazy;
    }s[MAXX];
    //根据需要维护什么进行改动(大概)
    inline void pushup(int i){
        s[i].sum=s[s[i].left].sum^s[s[i].right].sum^s[i].val;
    }
    inline void pushdown(int i){
        if(s[i].lazy){
            swap(s[i].left,s[i].right);
            if(s[i].left) s[s[i].left].lazy^=1;
            if(s[i].right) s[s[i].right].lazy^=1;
            s[i].lazy=0;
        }
    }
    inline int identify(int i){
        if(s[s[i].fa].left==i) return 0;
        if(s[s[i].fa].right==i) return 1;
        return -1;
    }
    inline void connect(int i,int f,int op){
        s[i].fa=f;
        if(op==1) s[f].right=i;
        if(op==0) s[f].left=i;
    }
    inline void rotate(int x){
        int y=s[x].fa;
        int z=s[y].fa;
        int opy=identify(y);
        int opx=identify(x);
        int u=0;
        if(opx==1) u=s[x].left;
        if(opx==0) u=s[x].right;
        connect(u,y,opx);
        connect(y,x,opx^1);
        connect(x,z,opy);
        pushup(y);
        pushup(x);
    }
    void pushall(int x){
        if(identify(x)!=-1) pushall(s[x].fa);
        pushdown(x);
    }
    inline void splay(int i){
        pushall(i);
        while(identify(i)!=-1){
            int up=s[i].fa;
            if(identify(up)==-1) rotate(i);
            else if(identify(i)==identify(up)) rotate(up),rotate(i);
            else rotate(i),rotate(i);
        }
    }
    //以上为splay的一些基本操作
    //下面是LCT的操作
    //构建一条从根到k的一条重链
    inline int access(int k){
        int temp=0;
        while(k){
            splay(k);
            s[k].right=temp;
            pushup(k);
            temp=k;
            k=s[k].fa;
        }
        return temp;
    }
    inline void makeroot(int k){
        access(k);
        splay(k);
        swap(s[k].left,s[k].right);
        if(s[k].left) s[s[k].left].lazy^=1;
        if(s[k].right) s[s[k].right].lazy^=1;
    }
    inline int findroot(int k){
        access(k);
        splay(k);
        while(s[k].left){
            pushdown(k);
            k=s[k].left;
        }
        splay(k);
        return k;
    }
    //询问或操作从x到y这条链
    //将从x到y这条链单独提出来，并将y变成根
    inline void split(int x,int y){
        makeroot(x);
        access(y);
        splay(y);
    }
    //返回x和y的lca
    inline int lca(int x,int y){
        access(x);
        return access(y);
    }
    //返回以r为根的情况下的x和y的lca
    inline int lca(int r,int x,int y){
        makeroot(r);
        access(x);
        return access(y);
    }
    inline bool link(int x,int y){
        makeroot(x);
        if(findroot(y)==x) return false;
        s[x].fa=y;
        return true;
    }
    inline bool cut(int x,int y){
        if(findroot(x)!=findroot(y)) return false;
        split(x,y);
        if(s[x].fa!=y||s[x].right) return false;
        s[x].fa=s[y].left=0;
        pushup(x);
        return true;
    }
}lct;

int n,m;

inline void solve(){
	scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&lct.s[i].val);
        lct.s[i].sum=lct.s[i].val;
    }

    while(m--){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==0){
            lct.split(x,y);
            printf("%d\n",lct.s[y].sum);
        }
        else if(op==1)
            lct.link(x,y);
        else if(op==2)
            lct.cut(x,y);
        else{
            lct.split(x,x);
            lct.s[x].val=lct.s[x].sum=y;
        }
    }
}

signed main(){
//	LL t;scanf("%lld",&t);
//	while(t--)
		solve();
	
	return 0;
}

智乃的LCA

题目传送门

题意

给出一棵树

多次询问 $lca(root,x,y)$ ，表示以 $root$ 为根的时候 $x$ 和 $y$ 的 lca 。

代码

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;

struct LCT{
    struct node{
        int fa,left,right,val,sum,lazy;
    }s[MAXX];
    //根据需要维护什么进行改动(大概)
    inline void pushup(int i){
        s[i].sum=s[s[i].left].sum^s[s[i].right].sum^s[i].val;
    }
    inline void pushdown(int i){
        if(s[i].lazy){
            swap(s[i].left,s[i].right);
            if(s[i].left) s[s[i].left].lazy^=1;
            if(s[i].right) s[s[i].right].lazy^=1;
            s[i].lazy=0;
        }
    }
    inline int identify(int i){
        if(s[s[i].fa].left==i) return 0;
        if(s[s[i].fa].right==i) return 1;
        return -1;
    }
    inline void connect(int i,int f,int op){
        s[i].fa=f;
        if(op==1) s[f].right=i;
        if(op==0) s[f].left=i;
    }
    inline void rotate(int x){
        int y=s[x].fa;
        int z=s[y].fa;
        int opy=identify(y);
        int opx=identify(x);
        int u=0;
        if(opx==1) u=s[x].left;
        if(opx==0) u=s[x].right;
        connect(u,y,opx);
        connect(y,x,opx^1);
        connect(x,z,opy);
        pushup(y);
        pushup(x);
    }
    void pushall(int x){
        if(identify(x)!=-1) pushall(s[x].fa);
        pushdown(x);
    }
    inline void splay(int i){
        pushall(i);
        while(identify(i)!=-1){
            int up=s[i].fa;
            if(identify(up)==-1) rotate(i);
            else if(identify(i)==identify(up)) rotate(up),rotate(i);
            else rotate(i),rotate(i);
        }
    }
    //以上为splay的一些基本操作
    //下面是LCT的操作
    //构建一条从根到k的一条重链
    inline int access(int k){
        int temp=0;
        while(k){
            splay(k);
            s[k].right=temp;
            pushup(k);
            temp=k;
            k=s[k].fa;
        }
        return temp;
    }
    inline void makeroot(int k){
        access(k);
        splay(k);
        swap(s[k].left,s[k].right);
        if(s[k].left) s[s[k].left].lazy^=1;
        if(s[k].right) s[s[k].right].lazy^=1;
    }
    inline int findroot(int k){
        access(k);
        splay(k);
        while(s[k].left){
            pushdown(k);
            k=s[k].left;
        }
        splay(k);
        return k;
    }
    //询问或操作从x到y这条链
    inline void split(int x,int y){
        makeroot(x);
        access(y);
        splay(y);
    }
    //返回x和y的lca
    inline int lca(int x,int y){
        access(x);
        return access(y);
    }
    //返回以r为根的情况下的x和y的lca
    inline int lca(int r,int x,int y){
        makeroot(r);
        access(x);
        return access(y);
    }
    inline bool link(int x,int y){
        makeroot(x);
        if(findroot(y)==x) return false;
        s[x].fa=y;
        return true;
    }
    inline bool cut(int x,int y){
        if(findroot(x)!=findroot(y)) return false;
        split(x,y);
        if(s[x].fa!=y||s[x].right) return false;
        s[x].fa=s[y].left=0;
        pushup(x);
        return true;
    }
}lct;

int n,m;

inline void solve(){
	scanf("%d",&n);
    for(int i=1;i<n;++i){
        int jj,kk;
        scanf("%d%d",&jj,&kk);
        lct.link(jj,kk);
    }

    scanf("%d",&m);
    while(m--){
        int r,x,y;
        scanf("%d%d%d",&r,&x,&y);
        printf("%d\n",lct.lca(r,x,y));
    }
}

signed main(){
//	LL t;scanf("%lld",&t);
//	while(t--)
		solve();
	
	return 0;
}

[SDOI2008]CAVE 洞穴勘测

题目传送门

题意

三种操作

  • 加边
  • 删边
  • 询问 $x$ 和 $y$ 是否连通

保证一直是树结构

代码

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;

struct LCT{
    struct node{
        int fa,left,right,val,sum,lazy;
    }s[MAXX];
    //根据需要维护什么进行改动(大概)
    inline void pushup(int i){
        s[i].sum=s[s[i].left].sum^s[s[i].right].sum^s[i].val;
    }
    inline void pushdown(int i){
        if(s[i].lazy){
            swap(s[i].left,s[i].right);
            if(s[i].left) s[s[i].left].lazy^=1;
            if(s[i].right) s[s[i].right].lazy^=1;
            s[i].lazy=0;
        }
    }
    inline int identify(int i){
        if(s[s[i].fa].left==i) return 0;
        if(s[s[i].fa].right==i) return 1;
        return -1;
    }
    inline void connect(int i,int f,int op){
        s[i].fa=f;
        if(op==1) s[f].right=i;
        if(op==0) s[f].left=i;
    }
    inline void rotate(int x){
        int y=s[x].fa;
        int z=s[y].fa;
        int opy=identify(y);
        int opx=identify(x);
        int u=0;
        if(opx==1) u=s[x].left;
        if(opx==0) u=s[x].right;
        connect(u,y,opx);
        connect(y,x,opx^1);
        connect(x,z,opy);
        pushup(y);
        pushup(x);
    }
    void pushall(int x){
        if(identify(x)!=-1) pushall(s[x].fa);
        pushdown(x);
    }
    inline void splay(int i){
        pushall(i);
        while(identify(i)!=-1){
            int up=s[i].fa;
            if(identify(up)==-1) rotate(i);
            else if(identify(i)==identify(up)) rotate(up),rotate(i);
            else rotate(i),rotate(i);
        }
    }
    //以上为splay的一些基本操作
    //下面是LCT的操作
    //构建一条从根到k的一条重链
    inline int access(int k){
        int temp=0;
        while(k){
            splay(k);
            s[k].right=temp;
            pushup(k);
            temp=k;
            k=s[k].fa;
        }
        return temp;
    }
    inline void makeroot(int k){
        access(k);
        splay(k);
        swap(s[k].left,s[k].right);
        if(s[k].left) s[s[k].left].lazy^=1;
        if(s[k].right) s[s[k].right].lazy^=1;
    }
    inline int findroot(int k){
        access(k);
        splay(k);
        while(s[k].left){
            pushdown(k);
            k=s[k].left;
        }
        splay(k);
        return k;
    }
    //询问或操作从x到y这条链
    inline void split(int x,int y){
        makeroot(x);
        access(y);
        splay(y);
    }
    //返回x和y的lca
    inline int lca(int x,int y){
        access(x);
        return access(y);
    }
    //返回以r为根的情况下的x和y的lca
    inline int lca(int r,int x,int y){
        makeroot(r);
        access(x);
        return access(y);
    }
    inline bool link(int x,int y){
        makeroot(x);
        if(findroot(y)==x) return false;
        s[x].fa=y;
        return true;
    }
    inline bool cut(int x,int y){
        if(findroot(x)!=findroot(y)) return false;
        split(x,y);
        if(s[x].fa!=y||s[x].right) return false;
        s[x].fa=s[y].left=0;
        pushup(x);
        return true;
    }
}lct;

int n,m;
char s[20];

inline void solve(){
	scanf("%d%d",&n,&m);
    while(m--){
        int x,y;
        scanf("\n%s%d%d",s+1,&x,&y);
        if(s[1]=='C')
            lct.link(x,y);
        else if(s[1]=='D')
            lct.cut(x,y);
        else{
            lct.makeroot(x);
            if(lct.findroot(y)==x)
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
}

signed main(){
//	LL t;scanf("%lld",&t);
//	while(t--)
		solve();
	
	return 0;
}
文章作者: Shaun
文章链接: http://shaun-2314.github.io/2022/08/25/lct-learning/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Shaun !
acm LCT
评论
  目录