记录编号	144328	评测结果	AAAAAAAAAA
题目名称	[国家集训队2011]旅游	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.105 s
提交时间	2014-12-22 16:12:11	内存使用	6.49 MiB

/****************************************\
* Author : hzoi_ztx
* Title  : [国家集训队2011]旅游(宋方睿)
* ALG    :
* CMT    :
* Data   :
\****************************************/
 
#include <cstdio>
#include <cstring>
 
int CH , NEG ;
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<'!') ;
	if (ret == 'M') ret += getchar() ;
	while (CH=getchar() , CH>'!') ;
}
 
#define  maxn     100010LL
#define  maxe     200010LL
#define  infi     0x7f7f7f7fLL
#define  max(a,b) ((a)>(b)?(a):(b))
#define  min(a,b) ((a)<(b)?(a):(b))
 
struct FST { int to , next , val ; } e[maxe] ;
int star[maxn] = {0} , tote = 1 ;/* ! */
void AddEdge(int u , int v , int w) {
	e[++tote].to = v ; e[tote].val = w ; e[tote].next = star[u] ; star[u] = tote ;
	e[++tote].to = u ; e[tote].val = w ; e[tote].next = star[v] ; star[v] = tote ;
}
 
int fa[maxn] = {0} , ch[maxn][2] = {0} ;
int val[maxn] = {0} , sum[maxn] = {0} ;
int maxv[maxn] = {0} , minv[maxn] = {0} ;
bool neg[maxn] = {0} ;

int belong[maxn] = {0} ;
 
#define null     0LL
#define left(u)  ch[u][0]
#define right(u) ch[u][1]
 
inline void exchange(int&u,int&v) {int w=u;u=v;v=w;}
inline bool isrt(int u) {
	return (!fa[u]) || ((left(fa[u])!=u)&&(right(fa[u])!=u)) ;
}
 
inline void Maintain(int u) {
	sum[u] = maxv[u] = minv[u] = val[u] ;
	if (left(u)) {
		sum[u] += sum[left(u)] ;
		maxv[u] = max(maxv[left(u)] , maxv[u]) ;
		minv[u] = min(minv[left(u)] , minv[u]) ;
	}
	if (right(u)) {
		sum[u] += sum[right(u)] ;
		maxv[u] = max(maxv[right(u)] , maxv[u]) ;
		minv[u] = min(minv[right(u)] , minv[u]) ;
	}
}
 
inline void Change(int u) {
	if (u) {
		neg[u] ^= true ;
		val[u] = -val[u] ;
		sum[u] = -sum[u] ;
		maxv[u] = -maxv[u] ;
		minv[u] = -minv[u] ;
		exchange(maxv[u] , minv[u]) ;
	}
}
 
inline void Clear(int u) {
	if (u && neg[u]) {
		Change(left(u)) ;
		Change(right(u)) ;
		neg[u] = false ;
	}
}
 
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) ;
}
 
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) ;
}
 
inline void Splay(int x) {
	Clear(x) ;
	int y , z ;
	while (!isrt(x)) {
		y = fa[x] , z = fa[y] ;
		if (isrt(y)) {
			Clear(y) , Clear(x) ;
			if (left(y) == x) zig(x) ; else zag(x) ;
		} else {
			Clear(z) , Clear(y) , Clear(x) ;
			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) ;
			}
		}
	}
	Maintain(x) ;
}
 
inline void Access(int u) {
	for (int v = null ; u ; u = fa[u]) {
		Splay(u) ; Clear(u) ;
		right(u) = v , v = u ; Maintain(u) ;
	}
}
 
int vis[maxn] = {0} ;
void BuildTree(int u) {
	vis[u] = true ;
	int p , v ;
	for (p=star[u] ; p ; p =e[p].next) {
		v = e[p].to ;
		if (!vis[v]) {
			fa[v] = u ;
			sum[v] = val[v] = e[p].val ;
			belong[p>>1] = v ;
			BuildTree(v) ;
		}
	}
}
 
void CHANGE(int u , int w) {
	u = belong[u] ; Splay(u) ; val[u] = w ;
}

void NEGATE(int u , int v) {
	Access(v) ;
	for (v = null ; u ; u = fa[u]) {
		Splay(u) ;
		if (!fa[u]) {
			Change(v) , Change(right(u)) ;
			Maintain(u) ;
			return ;
		}
		Clear(u) ;
		right(u) = v , v = u ; Maintain(u) ;
	}
}

void SUM(int u , int v) {
	Access(v) ;
	for (v = null ; u ; u = fa[u]) {
		Splay(u) ;
		if (!fa[u]) {
			printf("%d\n", sum[v]+sum[right(u)] ) ;
			return ;
		}
		Clear(u) ;
		right(u) = v , v = u ; Maintain(u) ;
	}
}
 
void MAX(int u , int v) {
	Access(v) ;
	for (v = null ; u ; u = fa[u]) {
		Splay(u) ;
		if (!fa[u]) {
			printf("%d\n", max(maxv[v] , maxv[right(u)])) ;
			return ;
		}
		Clear(u) ;
		right(u) = v , v = u ; Maintain(u) ;
	}
}
  
void MIN(int u , int v) {
	Access(v) ;
	for (v = null ; u ; u = fa[u]) {
		Splay(u) ;
		if (!fa[u]) {
			printf("%d\n", min(minv[v] , minv[right(u)])) ;
			return ;
		}
		Clear(u) ;
		right(u) = v , v = u ; Maintain(u) ;
	}
}

int n , i , u , v , w , Q ;
 
int main() {
    #define READ
    #ifdef  READ
        freopen("nt2011_travel.in" ,"r",stdin ) ;
        freopen("nt2011_travel.out","w",stdout) ;
    #endif
    read(n) ;
    for (i = 1 ; i < n ; i ++ ) {
    	read(u) , read(v) , read(w) ;
    	AddEdge(++u , ++v , w) ;
	}
	sum[null] = 0 ;
	maxv[null] = -infi ;
	minv[null] = infi ;
	BuildTree(1) ;
	read(Q) ;
	while ( Q -- ) {
		reads(i) , read(u) , read(v) ;
		u ++ , v ++ ;
		if (i == 'C') CHANGE(--u , --v) ;
		else if (i == 'N') NEGATE(u , v) ;
		else if (i == 'S') SUM(u , v) ;
		else if (i == 'M'+'A') MAX(u , v) ;
		else if (i == 'M'+'I') MIN(u , v) ;
	}
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}