BZOJ2049: [Sdoi2008]Cave 洞穴勘测

抓紧时间点技能树。。。。说好的不坑的维修数列看来省选前还是要坑掉了qwq

#include
using namespace std;
#define MAXN 50005
#define ls son[x][0]
#define rs son[x][1]
struct Splay{
    int fa[MAXN],son[MAXN][2];
    int st[MAXN];
    bool rev[MAXN];
    inline int which(int x){
        for(int i=0;i<2;i++)if(son[fa[x]][i]==x)return i;
        return -1;
    }
    inline void pushdown(int x){
        if(rev[x]){
            rev[x]^=1;rev[ls]^=1;rev[rs]^=1;
            swap(ls,rs);
        }
    }
    inline void rotate(int x){
        int f=fa[x],w=which(x)^1,c=son[x][w];
        fa[x]=fa[f];if(which(f)!=-1)son[fa[f]][which(f)]=x;
        fa[c]=f;son[f][w^1]=c;
        fa[f]=x;son[x][w]=f;
    }
    inline void splay(int x){
        int top=0;st[++top]=x;
        for(int i=x;which(i)!=-1;i=fa[i]){
            st[++top]=fa[i];
        }
        for(int i=top;i;i--)pushdown(st[i]);
        while(which(x)!=-1){
            int f=fa[x];
            if(which(f)!=-1){
                if(which(x)^which(f))rotate(x);
                else rotate(f);
            }
            rotate(x);
        }
    }
    void access(int x){
        int t=0;
        while(x){
            splay(x);
            rs=t;
            t=x;x=fa[x];
        }
    }
    void rever(int x){
        access(x);splay(x);rev[x]^=1;
    }
    void link(int x,int y){
        rever(x);fa[x]=y;splay(x);
    }
    void cut(int x,int y){
        rever(x);access(y);splay(y);son[y][0]=fa[x]=0;
    }
    int find(int x){
        access(x);
		splay(x);
        int y=x;
        while(son[y][0])y=son[y][0];
        return y;
    }
}T;
int n,m;
int main(){
    char ch[10];
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%s",ch);
        scanf("%d%d",&x,&y);
        if(ch[0]=='C')T.link(x,y);
        else if(ch[0]=='D')T.cut(x,y);
        else {
            if(T.find(x)==T.find(y))printf("Yes\n");
            else printf("No\n");
        }
    }
}
此条目发表在BZOJ, LCT分类目录。将固定链接加入收藏夹。