洞穴探测

小鱼儿 2021-12-23 07:51 239阅读 0赞

LCT模板

# include <stdio.h>
    # include <stdlib.h>
    # include <iostream>
    # include <algorithm>
    # include <string.h>
    # define IL inline
    # define RG register
    # define Fill(a, b) memset(a, b, sizeof(a))
    using namespace std;
    typedef long long ll;
    const int MAXN(1e5 + 10);
    namespace LCT{
        int S[MAXN];
        struct Tree{  int fa, ch[2], rev;  } t[MAXN];
    
        IL void Pushdown(RG int x){
            if(!t[x].rev) return;
            swap(t[x].ch[0], t[x].ch[1]);
            t[x].rev = 0; t[t[x].ch[0]].rev ^= 1; t[t[x].ch[1]].rev ^= 1;
        }
    
        IL bool Son(RG int x){  return t[t[x].fa].ch[1] == x;  }
    
        IL bool Isroot(RG int x){  return t[t[x].fa].ch[0] != x && t[t[x].fa].ch[1] != x;  }
    
        IL void Rot(RG int x){
            RG int y = t[x].fa, z = t[y].fa, c = Son(x);
            if(!Isroot(y)) t[z].ch[Son(y)] = x; t[x].fa = z;
            t[y].ch[c] = t[x].ch[!c]; t[t[y].ch[c]].fa = y;
            t[x].ch[!c] = y; t[y].fa = x;
        }
    
        IL void Splay(RG int x){
            RG int top = 0; S[++top] = x;
            for(RG int y = x; !Isroot(y); y = t[y].fa) S[++top] = t[y].fa;
            while(top) Pushdown(S[top--]);
            for(RG int y = t[x].fa; !Isroot(x); Rot(x), y = t[x].fa)
                if(!Isroot(y)) Son(x) ^ Son(y) ? Rot(x) : Rot(y);
        }
    
        IL void Access(RG int x){  for(RG int y = 0; x; y = x, x = t[x].fa) Splay(x), t[x].ch[1] = y;  }
    
        IL void Makeroot(RG int x){  Access(x); Splay(x); t[x].rev ^= 1;  }
    
        IL int Findroot(RG int x){  Access(x); Splay(x); while(t[x].ch[0]) x = t[x].ch[0]; return x;  }
    
        IL void Split(RG int x, RG int y){  Makeroot(x); Access(y); Splay(y);   }
    
        IL void Link(RG int x, RG int y){  Makeroot(x); t[x].fa = y;  }
    
        IL void Cut(RG int x, RG int y){  Split(x, y); t[x].fa = t[y].ch[0] = 0;  }
    };
    using namespace LCT;
    
    IL ll Read(){
        RG char c = getchar(); RG ll x = 0, z = 1;
        for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
        for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
        return x * z;
    }
    
    int n, m;
    
    int main(RG int argc, RG char* argv[]){
        RG char opt[10]; n = Read(); m = Read();
        while(m--){
            RG int x, y; scanf(" %s", opt); x = Read(); y = Read();
            if(opt[0] == 'C') Link(x, y);
            else if(opt[0] == 'D') Cut(x, y);
            else if(opt[0] == 'Q') puts(Findroot(x) == Findroot(y) ? "Yes" : "No");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/cjoieryl/p/8206379.html