学步园

传送门：【BZOJ】2631 tree

题目分析：LCT模板题~标记的维护和维护线段类似。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
 
#define rep( i , a , b ) for ( int i = ( a ) ;i <  ( b ) ;++ i )
#define rev( i , a , b ) for ( int i = ( a ) ;i >= ( b ) ;-- i )
#define For( i , a , b ) for ( int i = ( a ) ;i <= ( b ) ;++ i )
#define clr( a , x ) memset ( a , x , sizeof a )
 
typedef long long LL ;
 
const int MAXN = 100005 ;
const LL mod = 51061 ;
struct Node* null ;
 
struct Node {
	Node* c[2] ;
	Node* f ;
	int flip ;
	LL addv ;
	LL mulv ;
	LL size ;
	LL sum ;
	LL v ;
 
	void newnode ( int val ) {
		addv = 0 ;
		mulv = 1 ;
		size = 1 ;
		flip = 0 ;
		v = val ;
		sum = val ;
		f = null ;
		c[0] = c[1] = null ;
	}
 
	void mul_val ( LL val ) {
		if ( this == null ) return ;
		v *= val ;
		sum *= val ;
		addv *= val ;
		mulv *= val ;
		if ( v >= mod ) v %= mod ;
		if ( sum >= mod ) sum %= mod ;
		if ( addv >= mod ) addv %= mod ;
		if ( mulv >= mod ) mulv %= mod ;
	}
 
	void add_val ( LL val ) {
		if ( this == null ) return ;
		v += val ;
		sum += size * val ;
		addv += val ;
		if ( v >= mod ) v %= mod ;
		if ( sum >= mod ) sum %= mod ;
		if ( addv >= mod ) addv %= mod ;
	}
 
	void reverse () {
		std :: swap ( c[0] , c[1] ) ;
		flip ^= 1 ;
	}
 
	void push_up () {
		size = 1 + c[0]->size + c[1]->size ;
		sum = ( c[0]->sum + c[1]->sum + v ) % mod ;
	}
 
	void push_down () {
		if ( flip ) {
			c[0]->reverse () ;
			c[1]->reverse () ;
			flip = 0 ;
		}
		if ( 1 != mulv ) {
			c[0]->mul_val ( mulv ) ;
			c[1]->mul_val ( mulv ) ;
			mulv = 1 ;
		}
		if ( addv ) {
			c[0]->add_val ( addv ) ;
			c[1]->add_val ( addv ) ;
			addv = 0 ;
		}
	}
 
	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 rotate ( int d ) {
		Node* p = f ;
		Node* gp = p->f ;
		p->link_child ( c[d] , !d ) ;
		if ( !p->is_root () ) {
			if ( p == gp->c[0] ) gp->link_child ( this , 0 ) ;
			else				 gp->link_child ( this , 1 ) ;
		}else f = gp ;
		link_child ( p , d ) ;
		p->push_up () ;
	}
 
	void down () {
		if ( !is_root () ) f->down () ;
		push_down () ;
	}
 
	void splay () {
		down () ;
		while ( !is_root () ) {
			if ( f->is_root () ) {
				if ( this == f->c[0] ) rotate ( 1 ) ;
				else rotate ( 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 ) ;
				}
			}
		}
		push_up () ;
	}
 
	void access () {
		Node* o = this ;
		Node* x = null ;
		while ( o != null ) {
			o->splay () ;
			o->link_child ( x , 1 ) ;
			o->push_up () ;
			x = o ;
			o = o->f ;
		}
		splay () ;
	}
 
	void make_root () {
		access () ;
		reverse () ;
	}
 
	Node* find_root () {
		access () ;
		Node* o = this ;
		while ( o->c[0] != null ) {
			o->push_down () ;
			o = o->c[0] ;
		}
		return o ;
	}
 
	void cut () {
		access () ;
		c[0]->f = null ;
		c[0] = null ;
		push_up () ;
	}
 
	void cut ( Node* o ) {
		make_root () ;
		o->cut () ;
	}
 
	void link ( Node* o ) {
		make_root () ;
		f = o ;
	}
 
	void add ( Node* o , int val ) {
		make_root () ;
		o->access () ;
		o->add_val ( val ) ;
	}
 
	void mul ( Node* o , int val ) {
		make_root () ;
		o->access () ;
		o->mul_val ( val ) ;
	}
 
	int query ( Node* o ) {
		make_root () ;
		o->access () ;
		return o->sum ;
	}
};
 
Node memory_pool[MAXN] ;
Node* cur ;
Node* node[MAXN] ;
int n , q ;
 
void clear () {
	cur = memory_pool ;
	null = cur ++ ;
	null->newnode ( 0 ) ;
	null->size = 0 ;
}
 
void solve () {
	int u , v , x , y , val ;
	char buf[10] ;
	clear () ;
	For ( i , 1 , n ) {
		node[i] = cur ++ ;
		node[i]->newnode ( 1 ) ;
	}
	rep ( i , 1 , n ) {
		scanf ( "%d%d" , &u , &v ) ;
		node[u]->link ( node[v] ) ;
	}
	while ( q -- ) {
		scanf ( "%s" , buf ) ;
		if ( buf[0] == '+' ) {
			scanf ( "%d%d%d" , &x , &y , &val ) ;
			node[x]->add ( node[y] , val ) ;
		}else if ( buf[0] == '-' ) {
			scanf ( "%d%d%d%d" , &x , &y , &u , &v ) ;
			node[x]->cut ( node[y] ) ;
			node[u]->link ( node[v] ) ;
		}else if ( buf[0] == '*' ) {
			scanf ( "%d%d%d" , &x , &y , &val ) ;
			node[x]->mul ( node[y] , val ) ;
		}else {
			scanf ( "%d%d" , &x , &y ) ;
			printf ( "%d\n" , node[x]->query ( node[y] ) ) ;
		}
	}
}
 
int main () {
	scanf ( "%d%d" , &n , &q );solve () ;
	return 0 ;
}