学步园

传送门：【BZOJ】2049 [Sdoi2008]Cave 洞穴勘测

题目分析：模板题

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

const int MAXN = 10005 ;

struct Node* null ;

struct Node {
	Node* c[2] ;
	Node* f ;
	int flip ;

	void newnode () {
		c[0] = c[1] = f = null ;
		flip = 0 ;
	}

	void reverse () {
		if ( this == null ) return ;
		swap ( c[0] , c[1] ) ;
		flip ^= 1 ;
	}

	void link_child ( Node* o , int d ) {
		c[d] = o ;
		o->f = this ;
	}

	int is_root () {
		return f == null || f->c[0] != this && f->c[1] != this ;
	}

	void push_down () {
		if ( flip ) {
			c[0]->reverse () ;
			c[1]->reverse () ;
			flip = 0 ;
		}
	}

	void sign_down () {
		if ( !is_root () ) f->sign_down () ;
		push_down () ;
	}

	void rotate ( int d ) {
		Node* p = f ;
		Node* g = p->f ;
		p->link_child ( c[d] , !d ) ;
		if ( !p->is_root () ) {
			if ( p == g->c[0] ) g->link_child ( this , 0 ) ;
			else g->link_child ( this , 1 ) ;
		} else f = g ;
		this->link_child ( p , d ) ;
	}

	void splay () {
		sign_down () ;
		while ( !is_root () ) {
			if ( f->is_root () ) rotate ( this == f->c[0] ) ;
			else {
				if ( f == f->f->c[0] ) {
					if ( this == f->c[0] ) f->rotate ( 1 ) , rotate ( 1 ) ;
					else rotate ( 0 ) , rotate ( 1 ) ;
				} else {
					if ( this == f->c[1] ) f->rotate ( 0 ) , rotate ( 0 ) ;
					else rotate ( 1 ) , rotate ( 0 ) ;
				}
			}
		}
	}

	void access () {
		Node* o = this ;
		Node* x = null ;
		while ( o != null ) {
			o->splay () ;
			o->link_child ( x , 1 ) ;
			x = o ;
			o = o->f ;
		}
		splay () ;
	}

	Node* find_root () {
		access () ;
		Node* o = this ;
		while ( o->c[0] != null ) o = o->c[0] ;
		return o ;
	}

	void make_root () {
		access () ;
		reverse () ;
	}

	void cut () {
		access () ;
		c[0]->f = null ;
		c[0] = null ;
	}

	void cut ( Node* o ) {
		if ( o->find_root () != find_root () ) return ;
		make_root () ;
		o->cut () ;
	}

	void link ( Node* o ) {
		if ( o == this || o->find_root () == find_root () ) return ;
		make_root () ;
		f = o ;
	}

	void query ( Node* o ) {
		if ( o->find_root () == find_root () ) printf ( "Yes\n" ) ;
		else printf ( "No\n" ) ;
	}
} ;

Node pool[MAXN] ;
Node* node[MAXN] ;
Node* cur ;

int n , m ;

void clear () {
	cur = pool ;
	null = cur ++ ;
	null->newnode () ;
}

void solve () {
	char s[20] ;
	int x , y ;
	clear () ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		node[i] = cur ++ ;
		node[i]->newnode () ;
	}
	while ( m -- ) {
		scanf ( "%s%d%d" , s , &x , &y ) ;
		if ( s[0] == 'C' ) node[x]->link ( node[y] ) ;
		if ( s[0] == 'D' ) node[x]->cut ( node[y] ) ;
		if ( s[0] == 'Q' ) node[x]->query ( node[y] ) ;
	}
}

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;
	return 0 ;
}