LCT动态树

数据结构 动态树 LCT
算法
发布日期:   2022-05-11
更新日期:   2022-05-13
文章字数:   5.5k
阅读时长:   33 分
阅读次数:  

LCT

模板

在这里插入图片描述

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

struct node{
    int s[2],p,v;
    int sum,rev;
    #define ls tr[u].s[0]
    #define lx tr[x].s[0]
    #define rs tr[u].s[1]
    #define rx tr[x].s[1]
}tr[N];
int n,m,op,x,y;
bool inline isroot(int u){
    return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void inline pushup(int u){
    tr[u].sum=tr[ls].sum^tr[u].v^tr[rs].sum;
}
void inline pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void inline pushdown(int u){
    if(tr[u].rev){
        pushrev(ls),pushrev(rs);
        tr[u].rev=0;
    }
}
void inline rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void inline splay(int x){
    static int stk[N];
    int tt=0,t=x;
    stk[++tt]=t;
    while(!isroot(t))stk[++tt]=t=tr[t].p;
    while(tt)pushdown(stk[tt--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if( (tr[z].s[1]==y)^(tr[y].s[1]==x) )rotate(x);
            else rotate(y);
        }rotate(x);
    }
}
void inline access(int x){
    int z=x;
    for(int y=0;x;y=x,x=tr[x].p){
        splay(x);
        rx=y;
        pushup(x);
    }
    splay(z);
}
void inline makeroot(int x){
    access(x);
    pushrev(x);
}
int inline findroot(int u){
    access(u);
    while(ls)pushdown(u),u=ls;
    splay(u);
    return u;
}
void inline split(int x,int y){
    makeroot(x);
    access(y);
}
void inline link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void inline cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>tr[i].v;
    while(m--){
        cin>>op>>x>>y;
        if(op==0){
            split(x,y);
            cout<<tr[y].sum<<'\n';
        }
        if(op==1)link(x,y);
        if(op==2)cut(x,y);
        if(op==3){
            splay(x);
            tr[x].v=y;
            pushup(x);
        }
    }
}

化边权为点权+动态维护区间最大值编号+用编号删边

在这里插入图片描述

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,p[N],stk[N];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
struct Edge{
    int x,y,a,b;
    bool operator<(const Edge&t)const{
        return a<t.a;
    }
}e[N];
struct node{
    int s[2],p,v;
    int mx,rev;
    #define ls tr[u].s[0]
    #define rs tr[u].s[1]
    #define lx tr[x].s[0]
    #define rx tr[x].s[1]
}tr[N];
void pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void pushup(int u){
    tr[u].mx=u;
    int lmaxid=tr[ls].mx;
    int rmaxid=tr[rs].mx;
    if(tr[lmaxid].v>tr[tr[u].mx].v)tr[u].mx=lmaxid;
    if(tr[rmaxid].v>tr[tr[u].mx].v)tr[u].mx=rmaxid;
}
void pushdown(int u){
    if(tr[u].rev){
        pushrev(ls);
        pushrev(rs);
        tr[u].rev=0;
    }
}
bool isroot(int u){
    return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void splay(int x){
    int top=0,r=x;
    stk[++top]=r;
    while(!isroot(r))stk[++top]=r=tr[r].p;
    while(top)pushdown(stk[top--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if((tr[z].s[1]==y)^(tr[y].s[1]==x))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x){
    int z=x;
    for(int y=0;x;y=x,x=tr[y].p){
        splay(x);
        tr[x].s[1]=y,pushup(x);
    }
    splay(z);
}
void makeroot(int x){
    access(x);
    pushrev(x);
}
int findroot(int x){
    access(x);
    while(lx)pushdown(x),x=lx;
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y);
}
void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
signed 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,a,b;
        cin>>x>>y>>a>>b;
        e[i]={x,y,a,b};
    }
    sort(e+1,e+1+m);
    for(int i=1;i<=n+m;i++){
        p[i]=i;
        if(i>n)tr[i].v=e[i-n].b;
        tr[i].mx=i;
    }
    int ans=1e9;
    for(int i=1;i<=m;i++){
        int x=e[i].x,y=e[i].y,a=e[i].a,b=e[i].b;
        if(find(x)==find(y)){
            split(x,y);
            int t=tr[y].mx;
            if(tr[t].v>b){
                cut(t,e[t-n].x),cut(t,e[t-n].y);
                link(i+n,x),link(i+n,y);
            }
        }
        else{
            p[find(x)]=find(y);
            link(i+n,x),link(i+n,y);
        }
        if(find(1)==find(n)){
            split(1,n);
            ans=min(ans,a+tr[tr[n].mx].v);
        }
    }
    cout<<(ans==1e9?-1:ans);
}

lct求子树大小

在这里插入图片描述

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
struct node{
	int fa,son[2],siz,exsiz,rev;
}t[100050];
inline void update(int x)
{
	t[x].siz=t[t[x].son[0]].siz+t[t[x].son[1]].siz+t[x].exsiz+1;
}
inline void pushdown(int x)
{
	if(t[x].rev)
	{
		swap(t[x].son[0],t[x].son[1]);
		if(t[x].son[0]) t[t[x].son[0]].rev^=1;
		if(t[x].son[1]) t[t[x].son[1]].rev^=1;
		t[x].rev=0;
	}
}
inline bool isroot(int x)
{
	return t[t[x].fa].son[0]!=x&&t[t[x].fa].son[1]!=x;
}
inline int get(int x)
{
	return t[t[x].fa].son[1]==x;
}
inline void rotate(int x)
{
	int f=t[x].fa;int ff=t[f].fa;int gx=get(x);int gx2=get(f);
	if(!isroot(f))
	{
		t[ff].son[gx2]=x;
	}
	t[f].son[gx]=t[x].son[gx^1];
	t[t[x].son[gx^1]].fa=f;
	t[x].son[gx^1]=f;
	t[f].fa=x;
	t[x].fa=ff;
	update(f);
	update(x);
}
int st[100050];
inline void splay(int x)
{
	int top=0;
	int y=x;
	st[++top]=y;
	while(!isroot(y))
	{
		y=t[y].fa;
		st[++top]=y;
	}
	while(top)
	{
		pushdown(st[top--]);
	}
	while(!isroot(x))
	{
		int f=t[x].fa;
		if(isroot(f))
		{
			rotate(x);
		}
		else if(get(x)==get(f))
		{
			rotate(f);
			rotate(x);
		}
		else 
		{
			rotate(x);
			rotate(x);
		}
		update(x);
	}
}
inline void access(int x)
{
	for(int y=0;x;y=x,x=t[x].fa)
	{
		splay(x);
		t[x].exsiz+=t[t[x].son[1]].siz-t[y].siz;
		t[x].son[1]=y;
		update(x);
	}
}
inline void makeroot(int x)
{
	access(x);
	splay(x);
	t[x].rev^=1;
	pushdown(x);
}
inline void link(int x,int y)
{
	makeroot(x);
	makeroot(y);
	t[x].fa=y;
	t[y].exsiz+=t[x].siz;
	update(y);
}
inline void split(int x,int y)
{
	makeroot(x);
	access(y);
	splay(y);
}
int n,q;
int main()
{
	 scanf("%d%d",&n,&q);
	 while(q--)
	 {
	 	char typ;
	 	cin>>typ;
	 	if(typ=='A')
	 	{
	 		int x,y;
	 		scanf("%d%d",&x,&y);
	 		link(x,y);
		}
		else
		{
			int x,y;
			scanf("%d%d",&x,&y);
			split(x,y);
			t[y].son[0]=t[x].fa=0;
			update(y);
			makeroot(x);
			makeroot(y);
			long long ans=(long long)(t[x].siz)*(long long)(t[y].siz);
			printf("%lld\n",ans);
			t[x].fa=y;
			t[y].exsiz+=t[x].siz;
		}
	 }
	 return 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
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
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

struct node{
    int s[2],p,v;
    int sum,rev;
    #define ls tr[u].s[0]
    #define lx tr[x].s[0]
    #define rs tr[u].s[1]
    #define rx tr[x].s[1]
}tr[N];
int n,m,op,x,y;
bool inline isroot(int u){
    return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void inline pushup(int u){
    tr[u].sum=tr[ls].sum+tr[u].v+tr[rs].sum;
}
void inline pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void inline pushdown(int u){
    if(tr[u].rev){
        pushrev(ls),pushrev(rs);
        tr[u].rev=0;
    }
}
void inline rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void inline splay(int x){
    static int stk[N];
    int tt=0,t=x;
    stk[++tt]=t;
    while(!isroot(t))stk[++tt]=t=tr[t].p;
    while(tt)pushdown(stk[tt--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if( (tr[z].s[1]==y)^(tr[y].s[1]==x) )rotate(x);
            else rotate(y);
        }rotate(x);
    }
}
void inline access(int x){
    int z=x;
    for(int y=0;x;y=x,x=tr[x].p){
        splay(x);
        rx=y;
        pushup(x);
    }
    splay(z);
}
void inline makeroot(int x){
    access(x);
    pushrev(x);
}
int inline findroot(int u){
    access(u);
    while(ls)pushdown(u),u=ls;
    splay(u);
    return u;
}
void inline split(int x,int y){
    makeroot(x);
    access(y);
}
void inline link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void inline cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
int fa[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // cin>>n>>m;
    // for(int i=1;i<=n;i++)cin>>tr[i].v;
    // while(m--){
    //     cin>>op>>x>>y;
    //     if(op==0){
    //         split(x,y);
    //         cout<<tr[y].sum<<'\n';
    //     }
    //     if(op==1)link(x,y);
    //     if(op==2)cut(x,y);
    //     if(op==3){
    //         splay(x);
    //         tr[x].v=y;
    //         pushup(x);
    //     }
    // }
    cin>>n;
    int T=n+1;
    for(int i=1;i<=n+1;i++)tr[i].v=1;
    for(int i=1;i<=n;i++){
        cin>>fa[i];
        fa[i]=min(fa[i]+i,n+1);
        link(i,fa[i]);
    }
    cin>>m;
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            x++;
            split(x,T);
            cout<<tr[T].sum-1<<'\n';
        }
        else{
            int x,f;
            cin>>x>>f;
            x++;
            cut(x,fa[x]);
            f=min(T,f+x);
            fa[x]=f;
            link(x,f);
        }
    }
}

树上求割边割点数量

在这里插入图片描述

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
#include <cstdio>

#define N 200010
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]

inline void swap(int&a,int&b) {
	int tmp(a); a=b,b=tmp;
}

namespace Summer {
	int ch[N][2],fa[N],rev[N],val[N],sumv[N],mark[N];
	inline void reverse(int x) {
		if(x) {
			swap(lc(x),rc(x));
			rev[x]^=1;
		}
	}
	inline void NaCly_Fish_Orz(int x) {
		if(x) {
			val[x]=sumv[x]=0;
			mark[x]=1;
		}
	}
	inline void up(int x) {
		sumv[x]=sumv[lc(x)]+sumv[rc(x)]+val[x];
	}
	inline void down(int x) {
		if(rev[x]) {
			reverse(lc(x));
			reverse(rc(x));
			rev[x]=0;
		}
		if(mark[x]) {
			NaCly_Fish_Orz(lc(x));
			NaCly_Fish_Orz(rc(x));
			mark[x]=0;
		}
	}
	inline int nrt(int x) {
		return x==lc(fa[x])||x==rc(fa[x]);
	}
	void psa(int x) {
		if(nrt(x)) psa(fa[x]);
		down(x);
	}
	inline void rotate(int x) {
		int y(fa[x]),z(fa[y]),k(x==rc(y));
		ch[y][k]=ch[x][k^1],ch[x][k^1]=y;
		if(nrt(y)) ch[z][y==rc(z)]=x;
		if(ch[y][k]) fa[ch[y][k]]=y;
		fa[y]=x,fa[x]=z,up(y);
	}
	inline void splay(int x) {
		int y,z;
		for(psa(x);nrt(x);rotate(x)) {
			y=fa[x],z=fa[y];
			if(nrt(y)) rotate(x==rc(y)^y==rc(z)?x:y);
		} up(x);
	}
	inline void access(int x) {
		for(int y=0;x;x=fa[y=x]) {
			splay(x); rc(x)=y; up(x);
		}
	}
	inline void mrt(int x) {
		access(x); splay(x); reverse(x);
	}
	inline void link(int x,int y) {
		mrt(x); fa[x]=y;
	}
	inline void cut(int x,int y) {
		mrt(x); access(y); splay(y);
		fa[x]=lc(y)=0; up(y);
	}
}

namespace Pockets {
	int ch[N][2],fa[N],rev[N],val[N],sumv[N],st[N],num;
	inline void reverse(int x) {
		if(x) {
			swap(lc(x),rc(x));
			rev[x]^=1;
		}
	}
	inline void up(int x) {
		sumv[x]=sumv[lc(x)]+sumv[rc(x)]+val[x];
	}
	inline void down(int x) {
		if(rev[x]) {
			reverse(lc(x));
			reverse(rc(x));
			rev[x]=0;
		}
	}
	inline int nrt(int x) {
		return x==lc(fa[x])||x==rc(fa[x]);
	}
	void psa(int x) {
		if(nrt(x)) psa(fa[x]);
		down(x);
	}
	inline void rotate(int x) {
		int y(fa[x]),z(fa[y]),k(x==rc(y));
		ch[y][k]=ch[x][k^1],ch[x][k^1]=y;
		if(nrt(y)) ch[z][y==rc(z)]=x;
		if(ch[y][k]) fa[ch[y][k]]=y;
		fa[y]=x,fa[x]=z,up(y);
	}
	inline void splay(int x) {
		int y,z;
		for(psa(x);nrt(x);rotate(x)) {
			y=fa[x],z=fa[y];
			if(nrt(y)) rotate(x==rc(y)^y==rc(z)?x:y);
		} up(x);
	}
	inline void access(int x) {
		for(int y=0;x;x=fa[y=x]) {
			splay(x); rc(x)=y; up(x);
		}
	}
	inline void mrt(int x) {
		access(x); splay(x); reverse(x);
	}
	inline void link(int x,int y) {
		mrt(x); fa[x]=y;
	}
	inline void cut(int x,int y) {
		mrt(x); access(y); splay(y);
		fa[x]=lc(y)=0; up(y);
	}
	void print(int now) {
		if(now) {
			down(now);
			print(lc(now));
			st[++num]=now;
			print(rc(now));
		}
	}
}

int n,q,opt,u,v,last,tot,ans,SummerPockets;

int fa[N];
inline int find(int x) {
	return x==fa[x]?x:fa[x]=find(fa[x]);
}

inline void getEdge(int u,int v) {
	int x=find(u),y=find(v);
	if(x!=y) {
		ans=-1;
		return;
	}
	Summer::mrt(u);
	Summer::access(v);
	Summer::splay(v);
	ans=Summer::sumv[v];
}

inline void getPoint(int u,int v) {
	int x=find(u),y=find(v);
	if(x!=y) {
		ans=-1;
		return;
	}
	Pockets::mrt(u);
	Pockets::access(v);
	Pockets::splay(v);
	ans=Pockets::sumv[v];
}

inline void link(int u,int v) {
	int x=find(u),y=find(v);
	if(x==y) {
		Summer::mrt(u);
		Summer::access(v);
		Summer::splay(v);
		Summer::NaCly_Fish_Orz(v);
		
		getPoint(u,v);
		if(ans>2) {
			++SummerPockets;
			Pockets::mrt(u);
			Pockets::access(v);
			Pockets::splay(v);
			Pockets::num=0;
			Pockets::print(v);
			for(int i=1;i<Pockets::num;++i)
				Pockets::cut(Pockets::st[i],Pockets::st[i+1]);
			for(int i=1;i<=Pockets::num;++i)
				Pockets::link(Pockets::st[i],SummerPockets);
		}
	} else {
		++tot; fa[y]=x;
		Summer::val[tot]=1;
		Summer::link(u,tot);
		Summer::link(tot,v);
		
		Pockets::link(u,v);
	}
}

int main() {
	scanf("%d%d",&n,&q);
	tot=SummerPockets=n;
	for(int i=1;i<=n;++i)
		fa[i]=i,Pockets::val[i]=1;
	while(q--) {
		scanf("%d%d%d",&opt,&u,&v);
		u^=last,v^=last;
		switch(opt) {
			case 1: {
				link(u,v);
				break;
			}
			case 2: {
				getEdge(u,v);
				if(ans!=-1) last=ans;
				printf("%d\n",ans);
				break;
			}
			default: {
				getPoint(u,v);
				if(ans!=-1) last=ans;
				printf("%d\n",ans);
				break;
			}
		}
	}
	return 0;
}

LCT+LCA

在这里插入图片描述

1操作很容易联想到LCT的access，考虑对于剩下俩操作的维护，但其实对于树上点到根的路径权值具有可减性，于是维护这样一个距离，然后用树上差分回答2询问，因为一个点的子树在dfs序上是连续的一段，可以用线段树维护最大值回答3询问

这个题就成了3个板子的嵌套+巧妙的LCT，线段树和lca都是基础了不必再赘述

巧妙的LCT在于可以用这个题加深对access的理解，单独拿出access来说

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void access(int x) {
    for (int y = 0; x; y = x, x = fa[x]) {
        splay(x); rs = y; //pushup(x);
    }
}

void access(int x) {
    int c;
    for (int y = 0; x; y = x, x = fa[x]) {
        splay(x);
        if (rs) c = findrt(rs), SEG::change(1, 1, n, dfn[c], dfn[c] + siz[c] - 1, 1);
        if (rs = y) c = findrt(y), SEG::change(1, 1, n, dfn[c], dfn[c] + siz[c] - 1, -1);
    }
}

access实质是我们要对于x到根路径全部变成实边，我们要的是对于维护的信息进行修改

考虑性质，虚边有贡献，而实边没有贡献，在具体实现过程中，对于点x，遇到它的父亲到它为虚边则变实，然后整个子树到根节点的距离-1，然后把x的父亲原来连的实边的那个子树贡献+1，即可解决1操作

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define q(x, y) SEG::query(1, 1, n, x, y)
#define inf 1e9
using namespace std;
void file() {
    freopen("read.in", "r", stdin);
    freopen("write.out", "w", stdout);
}
const int N = 1e6 + 10;
inline int read() {
    int sym = 0, res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
struct EDGE {
    int u, v, nxt;
} edge[N];
int n, m, head[N], cnt, dfn[N], siz[N], depth[N], rev[N];
void add(int u, int v) {edge[++cnt] = (EDGE){u, v, head[u]}; head[u] = cnt;}
namespace SEG {
    int tmax[N], tag[N];
    #define ls x << 1
    #define rs x << 1 | 1
    void pushup(int x) {tmax[x] = max(tmax[ls], tmax[rs]);}
    void update(int x, int t) {tmax[x] += t; tag[x] += t;}
    void pushdown(int x, int l, int r, int mid) {
        if (tag[x]) {
            update(ls, tag[x]); update(rs, tag[x]); tag[x] = 0;
        }
    }
    void build(int x, int l, int r) {
        if (l == r) {tmax[x] = depth[rev[l]]; return;}
        int mid = l + r >> 1;
        build(ls, l, mid); build(rs, mid + 1, r);
        pushup(x);
    }
    void change(int x, int l, int r, int ln, int rn, int t) {
        if (ln <= l && r <= rn) {update(x, t); return;}
        int mid = l + r >> 1; pushdown(x, l, r, mid);
        if (mid >= ln) change(ls, l, mid, ln, rn, t);
        if (mid + 1 <= rn) change(rs, mid + 1, r, ln, rn, t);
        pushup(x);
    }
    int query(int x, int l, int r, int ln, int rn) {
        if (ln <= l && r <= rn) return tmax[x];
        int mid = l + r >> 1, res = 0; pushdown(x, l, r, mid);
        if (mid >= ln) res = max(res, query(ls, l, mid, ln, rn));
        if (mid + 1 <= rn) res = max(res, query(rs, mid + 1, r, ln, rn));
        return res;
    }
}
namespace LCT {
    int son[N][2], fa[N];
    #define ls son[x][0]
    #define rs son[x][1]
    bool l_r(int x) {return x == son[fa[x]][1];}
    bool isroot(int x) {return son[fa[x]][0] != x && son[fa[x]][1] != x;}
    int findrt(int x) {while (ls) x = ls; return x;}
    void rotate(int x) {
        int y = fa[x], z = fa[y], kind = l_r(x);
        if (!isroot(y)) son[z][l_r(y)] = x;
        son[y][kind] = son[x][kind ^ 1]; fa[son[x][kind ^ 1]] = y;
        son[x][kind ^ 1] = y; fa[y] = x; fa[x] = z;
    }
    void splay(int x) {
        for (int y = fa[x]; !isroot(x); y = fa[x]) {
            if (!isroot(y)) rotate(l_r(x) == l_r(y) ? y : x); rotate(x);
        }
    }
    void access(int x) {
        int c;
        for (int y = 0; x; y = x, x = fa[x]) {
            splay(x);
            if (rs) c = findrt(rs), SEG::change(1, 1, n, dfn[c], dfn[c] + siz[c] - 1, 1);
            if (rs = y) c = findrt(y), SEG::change(1, 1, n, dfn[c], dfn[c] + siz[c] - 1, -1);
        }
    }
}
namespace LCA {
    int top[N], son[N], fa[N];
    void dfs1(int u, int last) {
        depth[u] = depth[last] + 1; siz[u] = 1; fa[u] = last;
        for (int e = head[u]; e; e = edge[e].nxt) {
            int v = edge[e].v; if (v == last) continue; dfs1(v, u);
            siz[u] += siz[v]; if (siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    void dfs2(int u, int front) {
        dfn[u] = ++cnt; rev[cnt] = u; top[u] = front; if (son[u]) dfs2(son[u], front);
        for (int e = head[u]; e; e = edge[e].nxt) {
            int v = edge[e].v; if (v == fa[u] || v == son[u]) continue; dfs2(v, v);
        }
    }
    int lca(int x, int y) {
        while (top[x] != top[y]) depth[top[x]] < depth[top[y]] ? y = fa[top[y]] : x = fa[top[x]];
        return depth[x] < depth[y] ? x : y;
    }
}
int main() {
    n = read(); m = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(); add(u, v); add(v, u);
    }
    cnt = 0; LCA::dfs1(1, 0); LCA::dfs2(1, 1); cnt = 0; SEG::build(1, 1, n);
    for (int i = 1; i <= n; i++) LCT::fa[i] = LCA::fa[i];
    for (int i = 1; i <= m; i++) {
        int opt = read(), x = read();
        if (opt == 1) LCT::access(x);
        if (opt == 2) {
            int y = read(), lca = LCA::lca(x, y);
            printf("%d\n", q(dfn[x], dfn[x]) + q(dfn[y], dfn[y]) - 2 * q(dfn[lca], dfn[lca]) + 1);
        }
        if (opt == 3) {
            printf("%d\n", q(dfn[x], dfn[x] + siz[x] - 1));
        }
    }
    return 0;
}

LCT懒标记

在这里插入图片描述

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
const int mod=51061;
struct node{
    int s[2],p,v;
    int sum,rev,mul,add,sz;
    #define ls tr[u].s[0]
    #define lx tr[x].s[0]
    #define rs tr[u].s[1]
    #define rx tr[x].s[1]
}tr[N];
int n,m,op,x,y;
bool inline isroot(int u){
    return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void inline pushup(int u){
    tr[u].sum=(tr[ls].sum+tr[u].v+tr[rs].sum)%mod;
    tr[u].sz=tr[ls].sz+tr[rs].sz+1;
}
void inline pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void pushmul(int u,int v){
    tr[u].sum=tr[u].sum*v%mod;
    tr[u].v=tr[u].v*v%mod;
    tr[u].add=tr[u].add*v%mod;
    tr[u].mul=tr[u].mul*v%mod;
}
void pushadd(int u,int v){
    tr[u].sum=(tr[u].sum+tr[u].sz*v)%mod;
    tr[u].v=(tr[u].v+v)%mod;
    tr[u].add=(tr[u].add+v)%mod;
}
void inline pushdown(int u){
    if(tr[u].rev){
        pushrev(ls),pushrev(rs);
        tr[u].rev=0;
    }
    if(tr[u].mul!=1){
        pushmul(ls,tr[u].mul),pushmul(rs,tr[u].mul);
        tr[u].mul=1;
    }
    if(tr[u].add!=0){
        pushadd(ls,tr[u].add),pushadd(rs,tr[u].add);
        tr[u].add=0;
    }
}
void inline rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void inline splay(int x){
    static int stk[N];
    int tt=0,t=x;
    stk[++tt]=t;
    while(!isroot(t))stk[++tt]=t=tr[t].p;
    while(tt)pushdown(stk[tt--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if( (tr[z].s[1]==y)^(tr[y].s[1]==x) )rotate(x);
            else rotate(y);
        }rotate(x);
    }
}
void inline access(int x){
    int z=x;
    for(int y=0;x;y=x,x=tr[x].p){
        splay(x);
        rx=y;
        pushup(x);
    }
    splay(z);
}
void inline makeroot(int x){
    access(x);
    pushrev(x);
}
int inline findroot(int u){
    access(u);
    while(ls)pushdown(u),u=ls;
    splay(u);
    return u;
}
void inline split(int x,int y){
    makeroot(x);
    access(y);
}
void inline link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void inline cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)tr[i].mul=tr[i].v=tr[i].sz=tr[i].sum=1;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        link(x,y);
    }
    while(m--){
        char c;
        int v;
        cin>>c;
        if(c=='+'){
            cin>>x>>y>>v;
            split(x,y);
            pushadd(y,v);
        }
        if(c=='-'){
            cin>>x>>y;cut(x,y);
            cin>>x>>y;link(x,y);
        }
        if(c=='*'){
            cin>>x>>y>>v;
            split(x,y);
            pushmul(y,v);
        }
        if(c=='/'){
            cin>>x>>y;
            split(x,y);
            cout<<tr[y].sum<<'\n';
        }
    }
}

用动态树解决树链剖分问题

在这里插入图片描述

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
160
161
162
163
164
165
166
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define int long long
int n,m,p[N],stk[N];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
struct Edge{
    int x,y,a,b;
    bool operator<(const Edge&t)const{
        return a<t.a;
    }
}e[N];
struct node{
    int s[2],p,v;
    int max,min,sum,rev,lazy;
    #define ls tr[u].s[0]
    #define rs tr[u].s[1]
    #define lx tr[x].s[0]
    #define rx tr[x].s[1]
}tr[N];

void pushup(int u){
    tr[u].sum=tr[ls].sum+tr[u].v+tr[rs].sum;
    if(u>n)tr[u].max=tr[u].min=tr[u].v;
    else tr[u].max=-1e9,tr[u].min=1e9;
    if(ls){
        tr[u].max=max(tr[u].max,tr[ls].max);
        tr[u].min=min(tr[u].min,tr[ls].min);
    }
    if(rs){
        tr[u].max=max(tr[u].max,tr[rs].max);
        tr[u].min=min(tr[u].min,tr[rs].min);
    }
}
void pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void pushlazy(int u){
    tr[u].sum=-tr[u].sum;
    tr[u].max=-tr[u].max;
    tr[u].min=-tr[u].min;
    tr[u].v=-tr[u].v;
    swap(tr[u].max,tr[u].min);
    tr[u].lazy^=1;
}
void pushdown(int u){
    if(tr[u].rev){
        pushrev(ls);
        pushrev(rs);
        tr[u].rev=0;
    }
    if(tr[u].lazy){
        pushlazy(ls);
        pushlazy(rs);
        tr[u].lazy=0;
    }
}
bool isroot(int u){
    return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void splay(int x){
    int top=0,r=x;
    stk[++top]=r;
    while(!isroot(r))stk[++top]=r=tr[r].p;
    while(top)pushdown(stk[top--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if((tr[z].s[1]==y)^(tr[y].s[1]==x))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x){
    int z=x;
    for(int y=0;x;y=x,x=tr[y].p){
        splay(x);
        tr[x].s[1]=y,pushup(x);
    }
    splay(z);
}
void makeroot(int x){
    access(x);
    pushrev(x);
}
int findroot(int x){
    access(x);
    while(lx)pushdown(x),x=lx;
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y);
}
void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
void change(int x,int w){
    splay(x);
    tr[x].v=w;
    pushup(x);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    //for(int i=1;i<=n;i++)tr[i].max=-1e9,tr[i].min=1e9;
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a++,b++;
        tr[i+n].max=tr[i+n].min=tr[i+n].sum=tr[i+n].v=c;
        link(a,i+n),link(i+n,b);
    }
    cin>>m;
    while(m--){
        string op;
        int x,y;
        cin>>op>>x>>y;
        if(op=="C"){change(x+n,y);continue;}
        x++,y++;
        if(op=="N"){
            split(x,y);
            tr[y].max=-tr[y].max;
            tr[y].min=-tr[y].min;
            swap(tr[y].max,tr[y].min);
            tr[y].sum=-tr[y].sum;
            tr[y].v=-tr[y].v;
            tr[y].lazy^=1;
        }
        if(op=="SUM"){
            split(x,y);
            cout<<tr[y].sum<<'\n';
        }
        if(op=="MAX"){
            split(x,y);
            cout<<tr[y].max<<'\n';
        }
        if(op=="MIN"){
            split(x,y);
            cout<<tr[y].min<<'\n';
        }
    }
}
文章作者: 胡耀文
文章链接: https://hyw200199.github.io/2022/05/11/lct-dong-tai-shu/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 胡耀文 !
数据结构 动态树 LCT
赏
  目录