P2147 [SDOI2008] 洞穴勘测（LCT）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141825874

https://www.luogu.com.cn/problem/P2147

第一次学LCT，梳理一下。

LCT是基于splay的，所以Splay的两个基本函数都有：

  • Rotate：不同点在于如果 yy 的父亲是 zz ，需要判断是否在同一棵平衡树树里在连实边。但是 xx 的父亲一定为 zz

  • Splay：注意，要在对 xx 到当前平衡树根的路径倒序pushdown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Rotate(int x) {
	int y = fa[x], z = fa[y]; 
	int k = zh(x), w = son[x][k ^ 1]; 
	if(z && !isRoot(y)) son[z][zh(y)] = x; 
	if(w) son[y][k] = w, fa[w] = y; else son[y][k] = 0; 
	fa[x] = z; fa[y] = x; son[x][k ^ 1] = y; 
}
void Splay(int x) {
	stack<int>sta; sta.push(x); 
	for(int y = x; !isRoot(y); y = fa[y]) sta.push(fa[y]); 
	while(!sta.empty()) push_down(sta.top()), sta.pop(); 
	while(!isRoot(x)) {
		int y = fa[x], z = fa[y]; 
		if(!isRoot(y)) {
			if(zh(x) == zh(y)) Rotate(y); 
			else Rotate(x); 
		}
		Rotate(x); 
	}
}

其中LCT引入一些新函数：

  • access：把 xx 到根的路径弄成一棵平衡树。具体操作为每次先转到当前平衡树的根，然后把父亲转到根后的右儿子设置为自己。
1
2
3
4
5
void access(int x) {
	for(int y = 0; x; y = x, x = fa[x]) {
		Splay(x); son[x][1] = y; 
	}
}

其他一些函数：

  • makeRoot
    先access，在splay，然后对整棵平衡树翻转（遍历全变），打tag

  • isRoot
    父亲的左右儿子都不是自己

  • Link
    先把 xx 转到自己那棵树的根（makeRoot），然后令 fa(x)=yfa(x)=y

  • Cut
    先makeRoot(x)，再access(y)，现在平衡树里理论上只有两个点。然后先splay(y)，在设置 ls(y) = fa(x) = 0（ 我们access(y)后 x,yx,y 一定成父子关系（但关系未定） ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void makeRoot(int x) {
	access(x); Splay(x); rev[x] ^= 1; 
}
void Link(int x, int y) {
	makeRoot(x); fa[x] = y; 
}
void Cut(int x, int y) {
	makeRoot(x); access(y); Splay(y); son[y][0] = fa[x] = 0; 
}
int findRoot(int x) {
		access(x); Splay(x); 
		while(push_down(x), ls(x)) x = ls(x); 
		Splay(x); 
		return x; 
	}

需要push_down的地方：Splay和要在路径上走的时候