记录编号	145048	评测结果	AAAAAAAAAA
题目名称	[国家集训队2011]旅游	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	0.087 s
提交时间	2015-01-02 08:00:49	内存使用	53.89 MiB

#include <cstdio>

const int MAXN=100010;
char cha[50000000],*ptr=cha;
struct node{
	int to,next,v;
}E[MAXN<<1];
int line[MAXN]={0},tot=1;
inline void Insert(int x,int y,int v){
	tot++; E[tot].to=y; E[tot].next=line[x]; line[x]=tot; E[tot].v=v;
}

int  N=0,M=0;
int  Fa[MAXN]={0},ch[MAXN][2]={0},Belong[MAXN]={0};
int  Val[MAXN]={0},Min[MAXN]={0},Max[MAXN]={0},Sum[MAXN]={0};
bool Rev[MAXN]={0},Neg[MAXN]={0};

#define L(x) ch[x][0]
#define R(x) ch[x][1]

inline bool IsRoot(int x){
	return (Fa[x]==0) || (L(Fa[x])!=x&&R(Fa[x])!=x) ;
}

inline int max(int x,int y){
	if(x>y) return x;
	return y;
}
inline int min(int x,int y){
	if(x<y) return x;
	return y;
}
inline void swap(int &x,int &y){
	x=x^y,y=x^y,x=x^y;
}

inline int Read(){
	int x=0,flag=0;
	while((*ptr<48)&&(*ptr!='-')) ptr++;
	if(*ptr=='-') flag=1;
	else x=*ptr-48;
	ptr++;
	while(*ptr>47) x=x*10+*ptr++-48;
	if(flag) return -x;
	return x;
}

inline void Update(int x){
	Sum[x]=Max[x]=Min[x]=Val[x];
	if(L(x)){ Sum[x]+=Sum[L(x)]; Max[x]=max(Max[x],Max[L(x)]); Min[x]=min(Min[x],Min[L(x)]); }
	if(R(x)){ Sum[x]+=Sum[R(x)]; Max[x]=max(Max[x],Max[R(x)]); Min[x]=min(Min[x],Min[R(x)]); }
}

inline void Rotate(int x,bool d){
	int y=ch[x][d^1]; ch[x][d^1]=ch[y][d]; Fa[ch[x][d^1]]=x; ch[y][d]=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 Change(int x){
	if(x){
		Neg[x]^=1; Sum[x]=-Sum[x]; Val[x]=-Val[x]; Min[x]=-Min[x]; Max[x]=-Max[x];
		swap(Min[x],Max[x]); 
	}
}

inline void PushDown(int x){
	if(x && Neg[x]){
		Change(L(x)); Change(R(x)); Neg[x]=false;
	}
}

inline void Splay(int x){
	PushDown(x);
	int y=0,z=0;
	while(!IsRoot(x)){
		y=Fa[x],z=Fa[y];
		if(IsRoot(y)){
			PushDown(y); PushDown(x); 
			Rotate(y,L(y)==x);
		}
		else{
			PushDown(z); PushDown(y); PushDown(x); 
			if(L(z)==y){
				if(L(y)==x){ Rotate(z,1); Rotate(y,1); }
				else { Rotate(y,0); Rotate(z,1); }
			}else{
				if(L(y)==x){ Rotate(y,1); Rotate(z,0); }
				else { Rotate(z,0); Rotate(y,0); }
			}
		}
	}
	Update(x);
}

inline void Access(int u){
	for(int v=0; u ;u=Fa[u]){ 
		Splay(u); PushDown(u); 
		R(u)=v; v=u; Update(u);
	}
}

inline void DFS(int u){
	for(int i=line[u];i!=0;i=E[i].next){
		int p=E[i].to;
		if(p!=Fa[u]){
			Fa[p]=u; Val[p]=E[i].v; Belong[i>>1]=p;
			DFS(p);
		}
	}
}

inline void Turn(int u,int w){
	u=Belong[u]; Splay(u); Val[u]=w;
}

inline void NEGATE(int u,int v){
	Access(v);
	for(v=0;u!=0;u=Fa[u]){
		Splay(u);
		if(!Fa[u]){
			Change(v); Change(R(u)); Update(u); return;
		}
		PushDown(u); R(u)=v; v=u; Update(u);
	}
}

inline void Query_Max(int u,int v){
	Access(v);
	for(v=0;u!=0;u=Fa[u]){
		Splay(u);
		if(!Fa[u]){
			printf("%d\n",max(Max[v],Max[R(u)])); return;
		}
		PushDown(u); R(u)=v; v=u; Update(u);
	}
}

inline void Query_Min(int u,int v){
	Access(v);
	for(v=0;u!=0;u=Fa[u]){
		Splay(u);
		if(!Fa[u]){
			printf("%d\n",min(Min[v],Min[R(u)])); return;
		}
		PushDown(u); R(u)=v; v=u; Update(u);
	}
}

inline void Query_Sum(int u,int v){
	Access(v);
	for(v=0;u!=0;u=Fa[u]){
		Splay(u);
		if(!Fa[u]){
			printf("%d\n",Sum[v]+Sum[R(u)]); return;
		}
		PushDown(u); R(u)=v; v=u; Update(u);
	}
}

int main(){
	freopen("nt2011_travel.in" ,"r",stdin ) ;
    freopen("nt2011_travel.out","w",stdout) ;
    fread(ptr,1,50000000,stdin);
	N=Read();
	int x=0,y=0,v=0;
	for(int i=1;i< N;++i){
		x=Read()+1,y=Read()+1,v=Read();
		Insert(x,y,v); Insert(y,x,v);
	}
	Sum[0]=0;
	Max[0]=-0x3f3f3f3f;
	Min[0]= 0x3f3f3f3f;
	DFS(1);
	M=Read(); char a[10];
	while(M--){
		while(*ptr<48) ptr++;
		int x,y;
		if(*ptr=='C') ptr++,x=Read(),y=Read(),Turn(x,y);
		else if(*ptr=='N') ptr++,x=Read(),y=Read(),NEGATE(++x,++y);
		else if(*ptr=='S') ptr+=3,x=Read(),y=Read(),Query_Sum(++x,++y);
		else{
			ptr++;
			if(*ptr=='A') ptr+=2,x=Read(),y=Read(),Query_Max(++x,++y);
			else ptr+=2,x=Read(),y=Read(),Query_Min(++x,++y);
		}
	}
	return 0;
}