bzoj 2049: [Sdoi2008]Cave 洞穴勘测 (link-cut-tree)

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <math.h>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#define lowbit(x) (x&(-x))
#define ll __int64
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define LS son[0][rt]
#define RS son[1][rt]
#define FA fa[rt]
#define new_edge(a,b,c) edge[tot].t = b , edge[tot].v = c , edge[tot].next = head[a] , head[a] = tot ++
using namespace std;

const int maxn = 111111 ;

int son[2][maxn] , fa[maxn] , is[maxn] ;
int rev[maxn] ;

void reverse ( int rt ) {
    if ( !rt ) return ;
    rev[rt] ^= 1 ;
    swap ( RS , LS ) ;
}

void push_down ( int rt ) {
    if ( rev[rt] ) {
        reverse ( LS ) ;
        reverse ( RS ) ;
        rev[rt] = 0 ;
    }
}

void push_up ( int rt ) {
}

void init ( int rt ) {
    FA = LS = RS = rev[rt] = 0 ;
    is[rt] = 1 ;
}

void rot ( int rt , int c ) {
    int y = fa[rt] , z = fa[y] ;
    son[!c][y] = son[c][rt] ; fa[son[c][rt]] = y ;
    son[c][rt] = y ; fa[y] = rt ;
    fa[rt] = z ;
    if ( is[y] ) is[y] = 0 , is[rt] = 1 ;
    else son[y==son[1][z]][z] = rt ;
    push_up ( y ) ;
}

void down ( int rt ) {
    if ( !is[rt] ) down ( fa[rt] ) ;
    push_down ( rt ) ;
}

void splay ( int rt ) {
    down ( rt ) ;
    while ( !is[rt] ) {
        if ( is[fa[rt]] ) rot ( rt , rt == son[0][fa[rt]] ) ;
        else {
            int y = fa[rt] , z = fa[y] ;
            int c = ( rt == son[0][y] ) , d = ( y == son[0][z] ) ;
            if ( c == d ) rot ( y , c ) , rot ( rt , c ) ;
            else rot ( rt , c ) , rot ( rt , d ) ;
        }
    }
    push_up ( rt ) ;
}

int access ( int rt ) {
    int v = 0 ;
    for ( ; rt ; rt = fa[rt] ) {
        splay ( rt ) ;
        is[RS] = 1 ; is[v] = 0 ;
        RS = v ;
        v = rt ;
        push_up ( rt ) ;
    }
    return v ;
}

void change_root ( int rt ) {
    access ( rt ) ;
    splay ( rt ) ;
    reverse ( rt ) ;
}

int find_root ( int rt ) {
    while ( fa[rt] ) rt = fa[rt] ;
    return rt ;
}

int query ( int a , int b ) {
    return find_root ( a ) == find_root ( b ) ;
}

void cut ( int a , int b ) {
    if ( query ( a , b ) ) {
        change_root ( a ) ;
        access ( a ) ;//确保a,b不在同一条链上
        splay ( b ) ;
        fa[b] = 0 ;
    }
}

void add ( int a , int b ) {
    if ( !query ( a , b ) ) {
        change_root ( b ) ;
        fa[b] = a ;
    }
}

int main() {
    int n , m , i , j , k ;
    char op[11] ;
    scanf ( "%d%d" , &n , &m ) ;
    for ( i = 1 ; i <= n ; i ++ ) init ( i ) ;
    while ( m -- ) {
        scanf ( "%s" , op ) ;
        int a , b ;
        scanf ( "%d%d" , &a , &b ) ;
        if ( op[0] == ‘Q‘ ) {
            k = query ( a , b ) ;
            if ( k ) puts ( "Yes" ) ;
            else puts ( "No" ) ;
        }
        else if ( op[0] == ‘D‘ ) cut ( a , b ) ;
        else add ( a , b ) ;
    }
    return 0;
}