/****************************************\
* Author : ztx
* Title  : [国家集训队2012]tree(伍一鸣)
* ALG    : LCT
* CMT    :
* 这个么.....使劲打标记吧
* 先乘法后加法, 和线段树维护是差不多的
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [国家集训队2012]tree(伍一鸣)
* ALG    : LCT
* CMT    :
* 这个么.....使劲打标记吧
* 先乘法后加法, 和线段树维护是差不多的
* Time   :
\****************************************/

#include <cstdio>

int CH , NEG ;
inline int GETCHAR() {
	static const int LEN = 21000000 ;
	static char BUF[LEN] , *S = BUF , *T = BUF ;
	if (S == T) {
		T = (S=BUF)+fread(BUF , 1 , LEN , stdin) ;
		if (S == T) return EOF ;
	}
	return *S ++ ;
}

inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=GETCHAR() , CH<'!') ;
    if (CH == '-') NEG = true , CH = GETCHAR() ;
    while (ret = ret*10+CH-'0' , CH=GETCHAR() , CH>'!') ;
    if (NEG) ret = -ret ;
}

inline void reads(int& ret) {
	while (ret=GETCHAR() , ret<'!') ;
	while (CH=GETCHAR() , CH>'!') ;
}

#define  maxn    100010LL
#define  maxe    200010LL
#define  ansmod  51061

typedef unsigned int uint ;

struct FST { int to , next ; } e[maxe] ;
int star[maxn] = {0} , tote = 0 ;
void AddEdge(int u , int v) {
	e[++tote].to = v ; e[tote].next = star[u] , star[u] = tote ;
}

int fa[maxn] = {0} , ch[maxn][2] = {0} ;
bool rev[maxn] = {0} ;
uint size[maxn] = {0} , val[maxn] = {0} ;
uint mul[maxn] = {0} , add[maxn] = {0} , sum[maxn] = {0} ;

#define  null     0LL
#define  left(u)  ch[u][0]
#define  right(u) ch[u][1]

inline void Exchange(int& a , int& b) { int c = a ; a = b ; b = c ; }

inline bool Isrt(int u) { return (fa[u]==null)||(left(fa[u])!=u&&right(fa[u])!=u) ; }

inline void Maintain(int u) {
	if (!u) return ;
	sum[u] = val[u]%ansmod , size[u] = 1 ;
	if (left(u)) {
		sum[u] += sum[left(u)] , sum[u] %= ansmod ;
		size[u] += size[left(u)] ;
	}
	if (right(u)) {
		sum[u] += sum[right(u)] , sum[u] %= ansmod ;
		size[u] += size[right(u)] ;
	}
}

void Mul(int u , uint w) {
	if (!u) return ;
	val[u] *= w , val[u] %= ansmod ;
	sum[u] *= w , sum[u] %= ansmod ;
	mul[u] *= w , mul[u] %= ansmod ;
	add[u] *= w , add[u] %= ansmod ;
}

void Add(int u , uint w) {
	if (!u) return ;
	val[u] += w , val[u] %= ansmod ;
	sum[u] += w*size[u] , sum[u] %= ansmod ;
	add[u] += w , add[u] %= ansmod ;
}

inline void Clear(int u) {
	if (!u) return ;
	if (mul[u] != 1) {
		Mul(left(u) , mul[u]) ;
		Mul(right(u) , mul[u]) ;
		mul[u] = 1 ;
	}
	if (add[u]) {
		Add(left(u) , add[u]) ;
		Add(right(u) , add[u]) ;
		add[u] = 0 ;
	}
	if (rev[u]) {
		rev[u] = false ;
		rev[left(u)] ^= true ;
		rev[right(u)] ^= true ;
		Exchange(left(u) , right(u)) ;
	}
}

inline void zig(int x) {
    /* right rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[right(x)] = y ; left(y) = right(x) ; fa[y] = x ; right(x) = y ;
    Maintain(y) , Maintain(x) ;
}

inline void zag(int x) {
    /* left rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[left(x)] = y ; right(y) = left(x) ; fa[y] = x ; left(x) = y ;
    Maintain(y) , Maintain(x) ;
}

inline void Splay(int x) {
	Clear(x) ;
	int y , z ;
	while (!Isrt(x)) {
		y = fa[x] , z = fa[y] ;
		Clear(z) , Clear(y) , Clear(x) ;
		if (Isrt(y)) {
			if (left(y) == x) zig(x) ; else zag(x) ;
		} else {
			if (left(z) == y) {
				if (left(y) == x) zig(x) , zig(x) ;
				else zag(x) , zig(x) ;
			} else if (right(z) == y) {
				if (right(y) == x) zag(x) , zag(x) ;
				else zig(x) , zag(x) ;
			}
		}
	}
}

inline int Access(int u) {
	int v = null ;
	for ( ; u ; u = fa[u]) Splay(u) , right(u) = v , v = u , Maintain(u) ;
	return v ;
}

inline void Makeroot(int u) {
	Access(u) , Splay(u) , rev[u] ^= true ;
}

inline void Link(int u , int v) {
	Makeroot(u) , fa[u] = v ;
}

inline void Cut(int u , int v) {
	Makeroot(u) ; Access(v) , Splay(v) , fa[u] = left(v) = null ; Maintain(v) ;
}

bool vis[maxn] = {0} ;
void BuildTree(int u) {
	if (vis[u]) return ; vis[u] = true ;
	size[u] = val[u] = sum[u] = mul[u] = 1 ;
	int p , v ;
	for (p = star[u] ; p ; p = e[p].next) {
		v = e[p].to ;
		if (!vis[v]) {
			fa[v] = u ; BuildTree(v) ;
		}
	}
}

int n , Q , cmd , u , v , w , i ;

int main() {
	#define READ
	#ifdef  READ
		freopen("nt2012_wym_tree.in" ,"r",stdin ) ;
		freopen("nt2012_wym_tree.out","w",stdout) ;
	#endif

	read(n) , read(Q) ;
	for (i = 1 ; i < n ; i ++ ) {
		read(u) , read(v) ;
		AddEdge(u , v) , AddEdge(v , u) ;
	}
	BuildTree(1) ;
	while ( Q -- ) {
		reads(cmd) , read(u) , read(v) ;
		if (cmd == '+') {
			read(w) ;
			Makeroot(u) , Access(v) , Splay(v) ;
			Add(v , w) ;
		} else if (cmd == '-') {
			Cut(u , v) ; read(u) , read(v) ;
			Link(u , v) ;
		} else if (cmd == '*') {
			read(w) ;
			Makeroot(u) , Access(v) , Splay(v) ;
			Mul(v , w) ;
		} else if (cmd == '/') {
			Makeroot(u) , Access(v) , Splay(v) ;
			printf("%d\n", sum[v] ) ;
		}
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

• 相关文章
• 全局相关文章