LCT维护子树信息学习笔记
发表更新ICPC/CCPC / Notes13 分钟读完 (大约1996个字)

LCT维护子树信息学习笔记

参考博客：1

简述

LCT 可以维护子树的信息。以维护子树大小为例：

设 sz[x] 表示 LCT 中以点 $x$ 为根的子树的总大小，注意，虽然 $x$ 的虚儿子并不一定是原树中 $x$ 的儿子，但是其大小是一样的；设 si[x] 表示 LCT 中点 $x$ 的所有虚子树的大小之和，那么：

即子树总大小等于左右子树总大小之和加上所有虚子树的大小之和。

例如，下图的 LCT 中，$H$ 子树的大小等于 $G$ 子树的大小加上 $I$ 子树的大小加上 $J$ 子树的大小，即 $sz[H]=sz[G]+sz[I]+si[H]$.

那具体的，我们需要在哪些地方维护这个 sz 和 si 呢？sz 可以通过 pushup 简单地维护，而 si 和虚实关系有关，我们仅在 access 和 link 操作中修改了虚实关系；在 access 时，我们把原来的右儿子变成了虚儿子，把原来的一个虚儿子变成了右儿子，故加一下减一下即可；在 link 时，我们把 $x$ 置为了 $y$ 的一个新虚儿子，故 si[y] 加上 sz[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
struct Splay{
    int son[2], fa;
    int sz, si;
    // sz is total size of subtree rooted at x
    // si is size of imaginary subtrees of node x
    bool rev;
}tr[N];
inline void pushup(int x){
    if(x){
        tr[x].sz = tr[x].si + 1;
        if(tr[x].son[0])	tr[x].sz += tr[tr[x].son[0]].sz;
        if(tr[x].son[1])	tr[x].sz += tr[tr[x].son[1]].sz;
    }
}
inline void access(int x){ // connect x with the root of LCT
    for(int y = 0; x; y = x, x = tr[x].fa){
        splay(x);
        tr[x].si += tr[tr[x].son[1]].sz - tr[y].sz;
        tr[x].son[1] = y; pushup(x);
    }
}
inline void link(int x, int y){
    makeRoot(x); access(y); splay(y);
    if(findRoot(y) != x){
        tr[x].fa = y;
        tr[y].si += tr[x].sz;
        pushup(y);
    }
}

当然，有些题目并不是维护子树大小，而是子树的其他信息，但其思想大致如此。

练习

[BJOI2014]大融合

题目链接

这道题维护子树大小即可。查询时将 $(x,y)$ 这条边拎出来，此时 $(x,y)$ 就是一条实链，故答案就是 $(si[x]+1)(si[y]+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
#include<cstdio>
#include<stack>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 100005;

struct LinkCutTree{
	int sta[N], staTop;
	struct Splay{
		int son[2], fa;
		int sz, si;
		// sz is total size of subtree rooted at x
		// si is size of imaginary subtrees of node x
		bool rev;
	}tr[N];
#define which(x, y) (tr[y].son[1] == x)
	inline void pushup(int x){
		if(x){
			tr[x].sz = tr[x].si + 1;
			if(tr[x].son[0])	tr[x].sz += tr[tr[x].son[0]].sz;
			if(tr[x].son[1])	tr[x].sz += tr[tr[x].son[1]].sz;
		}
	}
	inline void pushdown(int x){
		if(tr[x].rev){
			if(tr[x].son[0]){
				tr[tr[x].son[0]].rev ^= 1;
				swap(tr[tr[x].son[0]].son[0], tr[tr[x].son[0]].son[1]);
			}
			if(tr[x].son[1]){
				tr[tr[x].son[1]].rev ^= 1;
				swap(tr[tr[x].son[1]].son[0], tr[tr[x].son[1]].son[1]);
			}
			tr[x].rev ^= 1;
		}
	}
	inline bool isRoot(int x){ return tr[tr[x].fa].son[0] != x && tr[tr[x].fa].son[1] != x; }
	inline void rotate(int x, int dir){ // dir == 0: left; dir == 1: right
		int y = tr[x].fa, z = tr[y].fa, B = tr[x].son[dir];
		if(!isRoot(y))	tr[z].son[which(y,z)] = x;
		tr[x].son[dir] = y; tr[y].son[dir^1] = B;
		tr[x].fa = z; tr[y].fa = x; tr[B].fa = y;
		pushup(y); pushup(x);
	}
	inline void splay(int x){ // rotate x to the root of its splay tree
		sta[staTop = 1] = x;
		for(int i = x; !isRoot(i); i = tr[i].fa)	sta[++staTop] = tr[i].fa;
		while(staTop)	pushdown(sta[staTop--]); // pushdown the tag
		while(!isRoot(x)){
			int y = tr[x].fa, z = tr[y].fa, dir1 = which(x,y)^1, dir2 = which(y,z)^1;
			if(isRoot(y))	rotate(x, dir1);
			else{
				if(dir1 == dir2)	rotate(y, dir2);
				else	rotate(x, dir1);
				rotate(x, dir2);
			}
		}
	}
	inline void access(int x){ // connect x with the root of LCT
		for(int y = 0; x; y = x, x = tr[x].fa){
			splay(x);
			tr[x].si += tr[tr[x].son[1]].sz - tr[y].sz;
			tr[x].son[1] = y; pushup(x);
		}
	}
	inline void makeRoot(int x){ // make x the root of original tree
		access(x); splay(x);
		tr[x].rev ^= 1; swap(tr[x].son[0], tr[x].son[1]); //splay::reverse an interval
		pushup(x);
	}
	inline int findRoot(int x){ // find the root of original tree
		access(x); splay(x);
		while(tr[x].son[0])	x = tr[x].son[0];
		return x;
	}
	inline void link(int x, int y){
		makeRoot(x); access(y); splay(y);
		if(findRoot(y) != x){
			tr[x].fa = y;
			tr[y].si += tr[x].sz;
			pushup(y);
		}
	}
	inline void cut(int x, int y){
		makeRoot(x); access(y); splay(y);
		if(tr[y].son[0] != x)	return; // not connected
		tr[y].son[0] = tr[x].fa = 0;
		pushup(y);
	}

	inline LL query(int x, int y){
		makeRoot(x); access(y); splay(y);
		return (tr[x].si + 1ll) * (tr[y].si + 1ll);
	}
}LCT;

int n, q;

int main(){
	scanf("%d%d", &n, &q);
	while(q--){
		char opt[2]; int x, y;
		scanf("%s%d%d", opt, &x, &y);
		if(opt[0] == 'A')	LCT.link(x, y);
		else	printf("%lld\n", LCT.query(x, y));
	}
	return 0;
}

首都

题目链接

由于重心和子树大小相关，这道题仍然维护子树大小。我们可以用并查集来记录每个点所在块的重心是谁，那问题变成如何维护重心。

我们知道重心的一个性质：两棵树连起来后的重心一定位于原来两个重心的连线上。于是，我们把原来两个重心的连线拎出来，在这上面二分——即在这棵 Splay 上向左向右走。我们可以记录一个 ls 和 rs，表示当前二分区间以左和以右的点的个数，那么，以 $x$ 为分界点时，左边一共有 sz[tr[x].son[0]]+ls 个点，右边一共有 sz[tr[x].son[1]]+rs 个点，如果它们都小于总大小的一半，那么 $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
136
#include<bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, q, ans;

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

struct LinkCutTree{
	int sta[N], staTop;
	struct Splay{
		int son[2], fa;
		int sz, si;
		// sz is total size of subtree rooted at x
		// si is size of imaginary subtrees of node x
		bool rev;
	}tr[N];
#define which(x, y) (tr[y].son[1] == x)
	inline void pushup(int x){
		if(x){
			tr[x].sz = tr[x].si + 1;
			if(tr[x].son[0])	tr[x].sz += tr[tr[x].son[0]].sz;
			if(tr[x].son[1])	tr[x].sz += tr[tr[x].son[1]].sz;
		}
	}
	inline void pushdown(int x){
		if(tr[x].rev){
			if(tr[x].son[0]){
				tr[tr[x].son[0]].rev ^= 1;
				swap(tr[tr[x].son[0]].son[0], tr[tr[x].son[0]].son[1]);
			}
			if(tr[x].son[1]){
				tr[tr[x].son[1]].rev ^= 1;
				swap(tr[tr[x].son[1]].son[0], tr[tr[x].son[1]].son[1]);
			}
			tr[x].rev ^= 1;
		}
	}
	inline bool isRoot(int x){ return tr[tr[x].fa].son[0] != x && tr[tr[x].fa].son[1] != x; }
	inline void rotate(int x, int dir){ // dir == 0: left; dir == 1: right
		int y = tr[x].fa, z = tr[y].fa, B = tr[x].son[dir];
		if(!isRoot(y))	tr[z].son[which(y,z)] = x;
		tr[x].son[dir] = y; tr[y].son[dir^1] = B;
		tr[x].fa = z; tr[y].fa = x; tr[B].fa = y;
		pushup(y); pushup(x);
	}
	inline void splay(int x){ // rotate x to the root of its splay tree
		sta[staTop = 1] = x;
		for(int i = x; !isRoot(i); i = tr[i].fa)	sta[++staTop] = tr[i].fa;
		while(staTop)	pushdown(sta[staTop--]); // pushdown the tag
		while(!isRoot(x)){
			int y = tr[x].fa, z = tr[y].fa, dir1 = which(x,y)^1, dir2 = which(y,z)^1;
			if(isRoot(y))	rotate(x, dir1);
			else{
				if(dir1 == dir2)	rotate(y, dir2);
				else	rotate(x, dir1);
				rotate(x, dir2);
			}
		}
	}
	inline void access(int x){ // connect x with the root of LCT
		for(int y = 0; x; y = x, x = tr[x].fa){
			splay(x);
			tr[x].si += tr[tr[x].son[1]].sz - tr[y].sz;
			tr[x].son[1] = y; pushup(x);
		}
	}
	inline void makeRoot(int x){ // make x the root of original tree
		access(x); splay(x);
		tr[x].rev ^= 1; swap(tr[x].son[0], tr[x].son[1]); //splay::reverse an interval
		pushup(x);
	}
	inline int findRoot(int x){ // find the root of original tree
		access(x); splay(x);
		while(tr[x].son[0])	x = tr[x].son[0];
		return x;
	}
	inline void link(int x, int y){
		makeRoot(x); access(y); splay(y);
		if(findRoot(y) != x){
			tr[x].fa = y;
			tr[y].si += tr[x].sz;
			pushup(y);
		}
	}
	inline void cut(int x, int y){
		makeRoot(x); access(y); splay(y);
		if(tr[y].son[0] != x)	return; // not connected
		tr[y].son[0] = tr[x].fa = 0;
		pushup(y);
	}

	inline int maintain(int x, int y){
		int g = 1e9, ls = 0, rs = 0;
		int _x = x, _y = y;
		makeRoot(x);
		int tot = tr[x].sz;
		access(y); splay(y);
		while(y){
			pushdown(y);
			int lt = ls + tr[tr[y].son[0]].sz;
			int rt = rs + tr[tr[y].son[1]].sz;
			if(max(lt, rt) <= tot / 2)	g = min(g, y);
			if(lt < rt)	ls += tr[tr[y].son[0]].sz + tr[y].si + 1, y = tr[y].son[1];
			else		rs += tr[tr[y].son[1]].sz + tr[y].si + 1, y = tr[y].son[0];
		}
		makeRoot(g);
		fa[g] = fa[_x] = fa[_y] = g;
		return g;
	}
}LCT;

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i++)	ans ^= i, fa[i] = i;
	while(q--){
		char opt[2]; int x, y;
		scanf("%s", opt);
		if(opt[0] == 'A'){
			scanf("%d%d", &x, &y);
			int gx = findfa(x), gy = findfa(y);
			LCT.link(x, y);
			ans ^= gx ^ gy;
			ans ^= LCT.maintain(gx, gy);
		}
		else if(opt[0] == 'Q'){
			scanf("%d", &x);
			printf("%d\n", LCT.findRoot(x));
		}
		else	printf("%d\n", ans);
	}
	return 0;
}

LCT维护子树信息学习笔记

http://xyfjason.github.io/blog-xcpc/2020/12/17/LCT维护子树信息学习笔记/

作者

xyfJASON

发布于

2020-12-17

更新于

2021-02-25

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×