当前位置：首页 > news >正文

P2147 [SDOI2008] 洞穴勘测（LCT）

news 2025/5/22 23:12:24

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

第一次学LCT，梳理一下。

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

Rotate：不同点在于如果 $y$ 的父亲是 $z$ ，需要判断是否在同一棵平衡树树里在连实边。但是 $x$ 的父亲一定为 $z$
Splay：注意，要在对 $x$ 到当前平衡树根的路径倒序pushdown

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：把 $x$ 到根的路径弄成一棵平衡树。具体操作为每次先转到当前平衡树的根，然后把父亲转到根后的右儿子设置为自己。

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
先把 $x$ 转到自己那棵树的根（makeRoot），然后令 $f a (x) = y$
Cut
先makeRoot(x)，再access(y)，现在平衡树里理论上只有两个点。然后先splay(y)，在设置 ls(y) = fa(x) = 0

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; }