记录编号	156950	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	1.331 s
提交时间	2015-04-06 21:24:57	内存使用	0.75 MiB

/****************************************\
* Author : ztx
* Title  : [cogs] 1583. [POJ3237]树的维护
* ALG    : LCT复习
* CMT    :
链上边权最大值
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& 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 ;
}
template <typename TP>inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}

#define  maxn  10010LL

int fa[maxn] , ch[maxn][2] ;
int val[maxn] , maxv[maxn] , minv[maxn] ;
bool rev[maxn] ;

#define  null     0LL
#define  left(u)  ch[u][0]
#define  right(u) ch[u][1]
#define  max(x,y) ((x)>(y)?(x):(y))
#define  min(x,y) ((x)<(y)?(x):(y))
#define  infi     0x7f7f7f7fLL

inline void Exchange(int&a,int&b) {int c=a;a=b;b=c;}
inline bool Isrt(int u) { return !fa[u]||(left(fa[u])!=u&&right(fa[u])!=u) ; }
inline void Reverse(int u) {
	if (!u) return ;
	rev[u]^=true , val[u]=-val[u] ;
	Exchange(maxv[u],minv[u]) , maxv[u]=-maxv[u] , minv[u]=-minv[u] ;
}
inline void Clear(int u) {
	if (!u || !rev[u]) return ;
	rev[u] = false , Reverse(left(u)) , Reverse(right(u)) ;
}
inline void Maintain(int u) {
	maxv[u] = minv[u] = val[u] ;
	if (left(u)) {
		maxv[u] = max(maxv[u],maxv[left(u)]) ;
		minv[u] = min(minv[u],minv[left(u)]) ;
	}
	if (right(u)) {
		maxv[u] = max(maxv[u],maxv[right(u)]) ;
		minv[u] = min(minv[u],minv[right(u)]) ;
	}
}
inline void Rot(int x , int d) {
	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[y]=x,fa[ch[x][d]]=y;
	ch[y][!d]=ch[x][d],ch[x][d]=y;
	Maintain(y) ;
}
inline void Splay(int x) {
int y , z ;
	Clear(x) ;
	while (!Isrt(x)) {
		y=fa[x] , z=fa[y] ;
		Clear(z) , Clear(y) , Clear(x) ;
		if (Isrt(y)) Rot(x,left(y)==x) ;
		else if (left(z)==y) {
			if (left(y)==x) Rot(y,1) ;
			else Rot(x,0) ; Rot(x,1) ;
		} else {
			if (right(y)==x) Rot(y,0) ;
			else Rot(x,1) ; Rot(x,0) ;
		}
	}
	Maintain(x) ;
}
inline void Access(int u) {
	for (int v=null;u;v=u,u=fa[u]) Splay(u),right(u)=v,Maintain(u) ;
}
inline void NodeChange(int u , int w) {
	Splay(u) , val[u] = w ; Maintain(u) ;
}
inline void ChainRev(int u , int v) {
	for (Access(v),v=null;u;v=u,u=fa[u]) {
		Splay(u) ;
		if (!fa[u])
			Reverse(v) , Reverse(right(u)) ;
		right(u)=v , Maintain(u) ;
	}
}
inline void ChainMax(int u , int v) {
	for (Access(v),v=null;u;v=u,u=fa[u]) {
		Splay(u) ;
		if (!fa[u])
			printf("%d\n", max(maxv[v],maxv[right(u)])) ;
		right(u)=v , Maintain(u) ;
	}
}

#define  maxm  10010LL
int belong[maxm] = {0} ;
struct FST { int to , next , len ; } e[maxm<<1] ;
int star[maxn] = {0} , tote = 1 ;
inline void AddEdge(int u , int v , int w) { e[++tote].to = v ; e[tote].len = w ; e[tote].next = star[u] ; star[u] = tote ; }
inline void GetPar(int u) {
	for (int p=star[u] ; p ; p=e[p].next)
		if (e[p].to != fa[u]) {
			belong[p>>1] = e[p].to ;
			maxv[e[p].to] = minv[e[p].to] = val[e[p].to] = e[p].len ;
			fa[e[p].to] = u ;
			GetPar(e[p].to) ;
		}
}

int main() {
int n , m , i , u , v , w , cmd ;
	#define READ
	#ifdef  READ
		freopen("maintaintree.in" ,"r",stdin ) ;
		freopen("maintaintree.out","w",stdout) ;
	#endif
	read(n) ;
	Rep (i,2,n) {
		read(u) , read(v) , read(w) ;
		AddEdge(u,v,w) ;
		AddEdge(v,u,w) ;
	}
	maxv[null] = -infi ;
	minv[null] = infi ;
	/*   QAQ我特么又犯了一遍这个错   */
	GetPar(1) ;
	while (true) {
		reads(cmd) ;
		if (cmd == 'D') break ;
		read(u) , read(v) ;
		if (cmd == 'C') NodeChange(belong[u],v) ;
		if (cmd == 'Q') ChainMax(u,v) ;
		if (cmd == 'N') ChainRev(u,v) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}