P2147 [SDOI2008]洞穴勘测

佚名 6年前 (2019-05-05) 随笔 1142人围观抢沙发百度已收录

比板子还裸的LCT

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+7;
int n,m,st[N];
struct tree{
    int ch[2],v,fa;
    bool re;
}t[N];
bool nroot(int x){
    return (t[t[x].fa].ch[0]==x)||(t[t[x].fa].ch[1]==x);
}
void rev(int x){
    swap(t[x].ch[0],t[x].ch[1]);
    t[x].re^=1;
}
void pushdown(int x){
    if(t[x].re){
        if(t[x].ch[0])rev(t[x].ch[0]);
        if(t[x].ch[1])rev(t[x].ch[1]);
        t[x].re=0;
    }
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int k=t[y].ch[1]==x;
    if(nroot(y))t[z].ch[t[z].ch[1]==y]=x;
    t[x].fa=z;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].fa=y;
    t[x].ch[k^1]=y;
    t[y].fa=x;
}
void splay(int x){
    int z=0,y=x;
    st[++z]=y;
    while(nroot(y))st[++z]=y=t[y].fa;
    while(z) pushdown(st[z--]);
    while(nroot(x)){
        y=t[x].fa;
        z=t[y].fa;
        if(nroot(y))
            rotate((t[y].ch[1]==x)^(t[z].ch[1]==y)?x:y);
        rotate(x);
    }
}
void access(int x){
    for(int y=0;x;y=x,x=t[x].fa){
        splay(x);
        t[x].ch[1]=y;
    }
}
void makeroot(int x){
    access(x);
    splay(x);
    rev(x);
}
int findroot(int x){
    access(x);
    splay(x);
    while(t[x].ch[0]){
        pushdown(x);
        x=t[x].ch[0];
    }
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
}
void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x) t[x].fa=y;
}
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)!=x||t[y].fa!=x||t[y].ch[0])return;
    t[y].fa=t[x].ch[1]=0;
}
int main(){
    cin>>n>>m;
    while(m--){
        int x,y;
        char op[10];
        scanf("%s%d%d",op,&x,&y);
        if(op[0]=='C'){
            link(x,y);
        }
        else if(op[0]=='Q'){
            if(x==y){
                puts("Yes");
                continue;
            }
            makeroot(x);
            if(findroot(y)==x)puts("Yes");
            else puts("No");
        }
        else {
            cut(x,y);
        }
    }
    return 0;
}