记录编号	223726	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.899 s
提交时间	2016-02-13 10:01:31	内存使用	0.90 MiB

#include<cstdio>
#include<cstring>
#define l(x) son[x][0]
#define r(x) son[x][1]
inline int MAX(int A,int B){return A>B?A:B;}
inline int MIN(int A,int B){return A<B?A:B;}
int shu,first[10010],fa[10010],id[10010],val[10010],son[10010][2];
char c[11];
inline bool is_root(int x){return !fa[x]||(l(fa[x])!=x&&r(fa[x])!=x);}
struct edge{
	int v,w,nx,id;
}o[20010];
inline void add(int u,int v,int w,int i){
	o[++shu].v=v,o[shu].w=w,o[shu].id=i,o[shu].nx=first[u],first[u]=shu;
}
inline void dfs(int x,int last){
	for(int i=first[x];i;i=o[i].nx)
		if(o[i].v!=last){
			fa[o[i].v]=x;
			id[o[i].id]=o[i].v;
			val[o[i].v]=o[i].w;
			dfs(o[i].v,x);
		}
}
bool mk[10010];
int mx[10010],mn[10010],s[10010];
inline void update(int x){
	if(x!=1) mx[x]=mn[x]=val[x];
	else mx[x]=-0x7fffffff,mn[x]=0x7fffffff;
	if(l(x)) mx[x]=MAX(mx[x],mx[l(x)]),mn[x]=MIN(mn[x],mn[l(x)]);
	if(r(x)) mx[x]=MAX(mx[x],mx[r(x)]),mn[x]=MIN(mn[x],mn[r(x)]);
}
inline void mark(int x){
	if(x){
		mk[x]^=1;
		mx[x]=-mx[x],mn[x]=-mn[x],val[x]=-val[x];
		mn[x]^=mx[x],mx[x]^=mn[x],mn[x]^=mx[x];
	}
}
inline void pushdown(int x){
	if(!x||!mk[x]) return;
	mk[x]=0;
	mark(l(x)),mark(r(x));
}
inline void rotate(int x,bool k){
	int y=son[x][k^1];
	son[x][k^1]=son[y][k];
	fa[son[x][k^1]]=x;
	son[y][k]=x;
	if(x==l(fa[x])) l(fa[x])=y;
	else if(x==r(fa[x])) r(fa[x])=y;
	fa[y]=fa[x],fa[x]=y;
	update(x);
}
inline void splay(int p){
	s[++s[0]]=p;
	for(int i=p;!is_root(i);i=fa[i]) s[++s[0]]=fa[i];
	while(s[0]) pushdown(s[s[0]--]);
	int x,y;
	while(!is_root(p)){
		x=fa[p],y=fa[x];
		if(is_root(x)) rotate(x,l(x)==p);
		else if((l(y)==x)==(l(x)==p)) rotate(y,l(y)==x),rotate(x,l(x)==p);
		else rotate(x,l(x)==p),rotate(y,l(y)==p);
	}
	update(p);//注意update！！！！！！
}
inline void access(int x){
	int nx=0;
	while(x){
		splay(x);
		r(x)=nx;
		update(x);
		nx=x,x=fa[x];
	}
}
inline void change(int x,int y){
	splay(x);
	val[x]=y;
	update(x);
}
inline void fan(int x,int y){
	access(x);
	int nx=0;
	while(y){
		splay(y);
		if(!fa[y]){
			mark(r(y)),mark(nx);
			update(y);
			return;
		}
		r(y)=nx;
		update(y);
		nx=y,y=fa[y];
	}
}
inline int qmax(int x,int y){
	access(x);
	int nx=0;
	while(y){
		splay(y);
		if(!fa[y]) return MAX(mx[r(y)],mx[nx]);
		r(y)=nx;
		update(y);
		nx=y,y=fa[y];
	}
}
int main(){
	freopen("maintaintree.in","r",stdin);
	freopen("maintaintree.out","w",stdout);
	int T,n,u,v,w;
    T=1;
	while(T--){
		scanf("%d",&n);
		shu=0,memset(first,0,sizeof(first));
		for(int i=1;i<n;++i) scanf("%d%d%d",&u,&v,&w),add(u,v,w,i),add(v,u,w,i);
		dfs(1,1);
		mx[0]=mx[1]=-0x7fffffff;
		mn[0]=mn[1]=0x7fffffff;
		fa[0]=fa[1]=0;
		for(int i=2;i<=n;++i)
		    mx[i]=mn[i]=val[i];
		for(int i=1;i<=n;++i)
		    l(i)=r(i)=0;
		scanf("%s",c);
		while(*c!='D'){
			scanf("%d%d",&u,&v);
			if(*c=='C') change(id[u],v);
			else if(*c=='Q') printf("%d\n",qmax(u,v));
			else fan(u,v);
			scanf("%s",c);
		}
	}
}