2049: [Sdoi2008]Cave 洞穴勘测

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 11970 Solved: 5988
[Submit][Status][Discuss]
Description
辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

Input
第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。

Output
对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）

Sample Input
样例输入1 cave.in
200 5
Query 123 127
Connect 123 127
Query 123 127
Destroy 127 123
Query 123 127
样例输入2 cave.in
3 5
Connect 1 2
Connect 3 1
Query 2 3
Destroy 1 3
Query 2 3
Sample Output
样例输出1 cave.out

No

Yes

No

很明显的LCT，我们直接维护一下连通性即可，并且不需要push_up，因为我们没有维护除了连通性之外的东西。

这道题也可以用可撤销的并查集+线段树。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long 
using namespace std;
const int N=1e5+10;
int n,m;
struct Link_Cut_Tree{
	int cnt,st[N];
	struct node{int ch[2],fa,re;}t[N];
	inline void push_re(int p){swap(t[p].ch[0],t[p].ch[1]); t[p].re^=1;}
	inline void push_down(int p){
		if(t[p].re){
			if(t[p].ch[0])	push_re(t[p].ch[0]);
			if(t[p].ch[1])	push_re(t[p].ch[1]);	t[p].re^=1;
		}
	}
	inline bool isroot(int x){return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;}
	inline void rotate(int x){
		int y=t[x].fa,z=t[y].fa,k=t[y].ch[1]==x,w=t[x].ch[!k];
		if(!isroot(y))	t[z].ch[t[z].ch[1]==y]=x; t[x].ch[!k]=y; t[y].ch[k]=w;
		if(w)	t[w].fa=y; t[y].fa=x; t[x].fa=z; 
	}
	inline void splay(int x){
		cnt=1; st[cnt]=x; int y=x;
		while(!isroot(y))	st[++cnt]=y=t[y].fa;
		while(cnt)	push_down(st[cnt--]);
		while(!isroot(x)){
			int y=t[x].fa,z=t[y].fa;
			if(!isroot(y))	rotate((t[y].ch[0]==x)^(t[z].ch[0]==y)?x:y); rotate(x);
		}
	}
	inline void access(int x){
		for(int y=0;x;x=t[y=x].fa) splay(x),t[x].ch[1]=y;
	}
	inline void makeroot(int x){access(x); splay(x); push_re(x);}
	inline int find(int x){
		access(x); splay(x); while(t[x].ch[0]) push_down(x),x=t[x].ch[0];
		splay(x); return x;
	}
	inline void split(int x,int y){makeroot(x); access(y); splay(y);}
	inline void link(int x,int y){makeroot(x); if(find(y)!=x) t[x].fa=y;}
	inline void cut(int x,int y){
		makeroot(x);
		if(find(y)==x&&t[y].fa==x&&!t[y].ch[0])	t[y].fa=t[x].ch[1]=0;
	} 
}tr;
signed main(){
	cin>>n>>m; char op[10]; int x,y;
	while(m--){
		scanf("%s %d %d",op,&x,&y);
		if(op[0]=='Q')	puts(tr.find(x)==tr.find(y)?"Yes":"No");
		else if(op[0]=='D')	tr.cut(x,y);
		else	tr.link(x,y);
	}		
	return 0;
}