Fork me on GitHub

「SDOI2008」Cave 洞穴勘测

发表于 | 分类于
字数统计: 704字 | 阅读时长 ≈ 4分钟

SDOI2008-洞穴勘测

Links there:SDOI2008 Cave

题意:要求你实现只有Link与Cut操作的,真正意义上的,$LCT$!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
using namespace std;
#define lc ch[u][0]
#define rc ch[u][1]
//#define local

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
inline char NextChar(void){
    char c = getchar();
    while(!isalpha(c)) c=getchar();
    return c;
}
///------------------head------------------

int n,m,op;
const int MAXN = 1e4+10;
struct LinkCutTree{
    int ch[MAXN][2],sum[MAXN],rev[MAXN],w[MAXN],fa[MAXN];
    inline bool isRson(int u){return ch[fa[u]][1] == u;}
    inline bool isRoot(int u){return (ch[fa[u]][0] != u && ch[fa[u]][1] != u);}
    inline void Reverse(int u){rev[u] ^= 1;swap(lc,rc);}
    inline void pushdown(int u){if(rev[u]){if (lc) Reverse(lc); if(rc)Reverse(rc); rev[u]=0;}}
    inline void pushup(int u){sum[u]=sum[lc]^sum[rc]^w[u];}
    inline void Update(int u){if (!isRoot(u)) Update(fa[u]); pushdown(u);}
/* ----------- Splay part ------------*/
    inline void rotate(int u){
        int fau = fa[u],ffau = fa[fau],d = isRson(u);
        fa[u]=ffau; if (!isRoot(fau)) ch[ffau][isRson(fau)] = u;
        fa[ch[fau][d] = ch[u][d^1]] = fau;
        fa[ch[u][d^1] = fau] = u;
        pushup(fau); pushup(u);
    }
    inline void Splay(int u){ //边Splay边向根传递信息
        Update(u);
        for (;(!isRoot(u));rotate(u)){
            if (!isRoot(fa[u]))
            rotate(isRson(fa[u])==isRson(u)?fa[u]:u);
        }
    }
/* ----------- LCT part ------------*/
    inline void access(int u){
        for(int f = 0; u; f = u,u = fa[u]){
            Splay(u);
            rc = f;
            pushup(u);
        }
    }
    inline void makeroot(int u){access(u);Splay(u);Reverse(u);}
    inline int find(int u){access(u);Splay(u);while(lc)pushdown(u),u=lc;return u;}
    inline void split(int x,int y){makeroot(x);access(y);Splay(y);}
    inline void link(int x,int y){makeroot(x);fa[x]=y;}
    inline void cut(int u,int v){split(u,v);if(fa[u]==v&&(!rc))fa[u]=ch[v][0]=0;pushup(v);}
}LCT;
signed main(signed argc, char *argv[]){
    #ifdef local
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    n=read(),m=read();
    rep(i,1,m){
    	char x = NextChar();
//    	putchar(x);puts("");
    	switch(x){
    		case 'C':{
    			int x=read(),y=read();
    			if (LCT.find(x) != LCT.find(y)) LCT.link(x,y);
    			break;
            }
            case 'Q':{
                int x=read(),y=read();
                printf("%s\n",LCT.find(x)==LCT.find(y)?"Yes":"No");
                break;
            }
            default :{
                int x=read(),y=read();
                if (LCT.find(x) == LCT.find(y)) LCT.cut(x,y);
                break;
            }
        }
    }
    #ifdef local 
    fclose(stdin); fclose(stdout);
    #endif
    return 0;
}