记录编号	144919	评测结果	AAAAAAAAAA
题目名称	1867.[国家集训队2011]旅游	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	0.104 s
提交时间	2014-12-31 08:29:28	内存使用	6.21 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=100010;

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 void Read(int& x){
	int f=0; x=0; char ch=getchar();
	while(ch< '0' || ch> '9'){ if(ch=='-'){ f=1; ch=getchar() ;break; } ch=getchar();}
	while(ch>='0' && ch<='9'){ x=x*10+ch-48; ch=getchar(); }
	if(f==1) x=-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) ;
	Read(N);
	int x=0,y=0,v=0;
	for(int i=1;i< N;++i){
		Read(x); Read(y); Read(v); x++; y++;
		Insert(x,y,v); Insert(y,x,v);
	}
	Sum[0]=0;
	Max[0]=-0x3f3f3f3f;
	Min[0]= 0x3f3f3f3f;
	DFS(1);
	Read(M); char a[10];
	while(M--){
		int x=0,y=0;
		scanf("%s",a);
		Read(x); Read(y); x++; y++;
		if(a[0]=='C'){ x--; y--; Turn(x,y); }
		else if(a[0]=='N'){ NEGATE(x,y); }
		else if(a[0]=='S'){ Query_Sum(x,y); }
		else if(a[1]=='I'){ Query_Min(x,y); }
		else if(a[1]=='A'){ Query_Max(x,y); }
	}
	return 0;
}