【LCT模板题】Cave 洞穴勘测

Link-Cut-Tree

传送门：BZOJ2049 CodeVS1839

思路：LCT模板题

讲解看dalao的Blog（我懒得写了）：ZZSdalao

注意：判断是不是转到根时不要搞错条件。

代码如下：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 300000
int n,m,x,y,top,fa[N],stk[N],rev[N],son[N][2];
char ch;
bool isroot(int x){return son[fa[x]][0]!=x && son[fa[x]][1]!=x;}
void pushdown(int x){if (rev[x]){swap(son[x][0],son[x][1]); rev[son[x][0]]^=1; rev[son[x][1]]^=1;} rev[x]=0;}
void rotate(int x,int w){
	int y=fa[x];
	son[y][w^1]=son[x][w]; if (son[x][w]) fa[son[x][w]]=y;
	fa[x]=fa[y]; if (!isroot(y)){if (y==son[fa[y]][0]) son[fa[y]][0]=x; else son[fa[y]][1]=x;}
	fa[y]=x; son[x][w]=y;
}
void splay(int x){
	stk[++top]=x; for (int y=x;!isroot(y);y=fa[y]) stk[++top]=fa[y];
	for (;top;top--) pushdown(stk[top]);
	for (int y=fa[x];!isroot(x);y=fa[x]){
		if (isroot(y)){if (x==son[y][0]) rotate(x,1); else rotate(x,0);}
		else{
			if (x==son[y][0]){if (y==son[fa[y]][0]){rotate(y,1); rotate(x,1);} else{rotate(x,1); rotate(x,0);}}
			else{if (y==son[fa[y]][0]){rotate(x,0); rotate(x,1);} else{rotate(y,0); rotate(x,0);}}
		}
	}
}
void access(int x){for (int t=0;x;x=fa[x]){splay(x); son[x][1]=t; t=x;}}
void setroot(int x){access(x); splay(x); rev[x]^=1;}
void link(int x,int y){setroot(x); fa[x]=y;}
void cut(int x,int y){setroot(x); access(y); splay(y); fa[x]=son[y][0]=0;}
inline int find(int x){access(x); splay(x); for (;son[x][0];x=son[x][0]); return x;}
bool query(int x,int y){x=find(x); y=find(y); return x==y;}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		char ch;
		for (ch=getchar();ch!='Q' && ch!='C' && ch!='D';ch=getchar());
		if (ch=='Q'){for (ch=getchar();ch>='a' && ch<='z';ch=getchar()); scanf("%d%d",&x,&y); puts(query(x,y)?"Yes":"No");}
		if (ch=='C'){for (ch=getchar();ch>='a' && ch<='z';ch=getchar()); scanf("%d%d",&x,&y); link(x,y);}
		if (ch=='D'){for (ch=getchar();ch>='a' && ch<='z';ch=getchar()); scanf("%d%d",&x,&y); cut(x,y);}
	}
	
	return 0;
}