NC20311. [SDOI2008]CAVE 洞穴勘测
描述
输入描述
第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。
以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1 ≤ u, v ≤ n且u≠v) 分别表示两个洞穴的编号。
输出描述
对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）
示例1
输入:
200 5 Query 123 127 Connect 123 127 Query 123 127 Destroy 127 123 Query 123 127
输出:
No Yes No
示例2
输入:
3 5 Connect 1 2 Connect 3 1 Query 2 3 Destroy 1 3 Query 2 3
输出:
Yes No
C++ 解法, 执行用时: 161ms, 内存消耗: 892K, 提交时间: 2022-03-09 15:33:05
#include<bits/stdc++.h>
#define lc ch[x][0]
#define rc ch[x][1]
#define int long long
using namespace std;
const int maxn=1e4+9;
int fa[maxn], ch[maxn][2], st[maxn];
bool r[maxn];
bool nroot(int x){
return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
}
void pushr(int x){
int t=lc; lc=rc, rc=t, r[x]^=1;
}
void pushdown(int x){
if(r[x]){
if(lc)pushr(lc);
if(rc)pushr(rc);
r[x]=0;
}
}
void rotate(int x){
int y=fa[x], z=fa[y], k=(ch[y][1]==x), w=ch[x][!k];
if(nroot(y)) ch[z][ch[z][1]==y]=x;
ch[x][!k]=y, ch[y][k]=w;
if(w) fa[w]=y;
fa[y]=x, fa[x]=z;
}
void splay(int x){
int y=x,z=0;
st[++z]=y;
while(nroot(y)) st[++z]=y=fa[y];
while(z)pushdown(st[z--]);
while(nroot(x)){
y=fa[x], z=fa[y];
if(nroot(y))
rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
rotate(x);
}
}
void access(int x){
for(int y=0;x;x=fa[y=x])
splay(x),rc=y;
}
void makeroot(int x){
access(x), splay(x), pushr(x);
}
void link(int x,int y){
makeroot(x), fa[x]=y;
}
int findroot(int x){//找根（在真实的树中的）
access(x), splay(x);
while(lc) pushdown(x),x=lc;
splay(x);
return x;
}
void split(int x,int y){//提取路径, 使x−y的路径成为一个Splay（y为根）
makeroot(x), access(y), splay(y);
}
void cut(int x,int y){
split(x, y), fa[x]=ch[y][0]=0;
}
string s;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n,m,x,y;
cin>>n>>m;
while(m--){
cin>>s>>x>>y;
if(s[0]=='Q') makeroot(x), cout<<(findroot(y)==x?"Yes":"No")<<'\n';
else if(s[0]=='C') link(x, y);
else cut(x,y);
}
return 0;
}