既见君子

BZOJ2049 LCT裸题

刚学了LCT，练一练\ ( >O< ) /

#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
//LCT裸题，主要是看板
const int INF=100000+5;
#define name "2049"
int n,m;
struct zzk{
    bool rev;
    zzk *ch[2],*pre;
    void put_rev(){
        rev^=1;
    }
    void pushdown(){
        if(rev){
            ch[0]->put_rev();
            ch[1]->put_rev();
            swap(ch[0],ch[1]);
            rev=0;
        }
    }
} rnil;
zzk *nil=&rnil;
zzk tree[INF];
namespace LCT{
    void init(zzk *cur){
        cur->ch[0]=cur->ch[1]=cur->pre=nil;
        cur->rev=0;
    }
    void init(){
        for(int i=1;i<=n;++i) init(&tree[i]);
    }
    bool isroot(zzk *cur){
        return cur->pre->ch[0]!=cur&&cur->pre->ch[1]!=cur;
    }
    void rotate(zzk *now){
        zzk *fa=now->pre,*gfa=fa->pre;
        int d=fa->ch[1]==now;
        if(!isroot(fa))
            gfa->ch[gfa->ch[1]==fa]=now;
        now->pre=gfa;
        fa->pre=now;
        fa->ch[d]=now->ch[d^1];
        now->ch[d^1]->pre=fa;
        now->ch[d^1]=fa;
    }
    stack<zzk*> str;
    void splay(zzk *now){
        zzk *tmp=now;
        str.push(tmp);
        while(!isroot(tmp)){
            tmp=tmp->pre;
            str.push(tmp);
        }
        while(!str.empty()){
            str.top()->pushdown();
            str.pop();
        }
        while(!isroot(now)){
            zzk *fa=now->pre,*gfa=fa->pre;
            if(!isroot(fa)){
                if((fa->ch[1]==now)^(gfa->ch[1]==fa)) rotate(now);
                else rotate(fa);
            }
            rotate(now);
        }
    }
    void access(zzk *cur){
        for(zzk *son=nil;cur!=nil;cur=cur->pre){
            splay(cur);
            cur->ch[1]=son;
            son=cur;
        }
    }
    void makeroot(zzk *cur){
        access(cur);
        splay(cur);
        cur->put_rev();
    }
    void link(zzk *u,zzk*v){
        makeroot(u);
        u->pre=v;
        access(u);
    }
    void cut(zzk *u,zzk *v){
        makeroot(u);
        access(v);
        splay(v);
        u->pre=nil;
        v->ch[0]=nil;
    }
    zzk *find(zzk *cur){
        access(cur);
        splay(cur);
        while(cur->ch[0]!=nil) cur=cur->ch[0];
        return cur;
    }
    bool together(int u,int v){
        return (find(&tree[u])==find(&tree[v]));
    }
}
int main(){
    int x,y;
    char s[10];
    freopen(name".in","r",stdin);
    scanf("%d%d",&n,&m);
    LCT::init();
    for(int i=1;i<=m;++i){
        scanf("%s%d%d",s,&x,&y);
        if(s[0]=='C') LCT::link(&tree[x],&tree[y]);
        else if(s[0]=='D') LCT::cut(&tree[x],&tree[y]);
        else LCT::together(x,y)?printf("Yes\n"):printf("No\n");
    }
}