记录编号	304410	评测结果	AAAAAAAAAA
题目名称	[国家集训队2011]旅游	最终得分	100
用户昵称	LOSER	是否通过	通过
代码语言	C++	运行时间	0.474 s
提交时间	2016-09-08 14:08:11	内存使用	10.00 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define maxn 100010
#define Inf 0x7f7f7f7f
#define MIN(a,b) (a<b?a:b)
#define MAX(a,b) (a>b?a:b)
int n,w[maxn];
struct Edge{int to,next,dis,num;}e[maxn<<1];
int head[maxn],len;
void Addedge(int x,int y,int z,int id){
	e[++len].to=y;
	e[len].num=id;
	e[len].dis=z;
	e[len].next=head[x];
	head[x]=len;
}
struct Tree{
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define mid  ((l+r)>>1)
	int s,t,Q,W,lazy[maxn<<2],Min[maxn<<2],Max[maxn<<2],sum[maxn<<2];
	void Swap(int &x,int &y){
		int temp=-x;
		x=-y;
		y=temp;	
	}
	void Update(int rt){
		if(lazy[rt]){
			Swap(Min[rt<<1],Max[rt<<1]);
			Swap(Min[rt<<1|1],Max[rt<<1|1]);
			sum[rt<<1]=-sum[rt<<1],sum[rt<<1|1]=-sum[rt<<1|1];
			lazy[rt<<1]^=1;  lazy[rt<<1|1]^=1;
		}	
		lazy[rt]=0;
	}
	void negate(int rt,int l,int r){
		if(s<=l&&t>=r){
			Swap(Min[rt],Max[rt]);
			sum[rt]=-sum[rt];
			lazy[rt]^=1;
			return;	
		}	
		Update(rt);
		if(s<=mid)negate(lson);
		if(t>mid) negate(rson);
		Min[rt]=MIN(Min[rt<<1],Min[rt<<1|1]);
		Max[rt]=MAX(Max[rt<<1],Max[rt<<1|1]);
		sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	}
	void Insert(int rt,int l,int r){
		if(l==r){
			Min[rt]=Max[rt]=sum[rt]=W;
			return;	
		}
		Update(rt);
		if(Q<=mid)Insert(lson);
		else Insert(rson);
		Min[rt]=MIN(Min[rt<<1],Min[rt<<1|1]);
		Max[rt]=MAX(Max[rt<<1],Max[rt<<1|1]);
		sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	}	
	int querymin(int rt,int l,int r){
		if(s<=l&&t>=r)return Min[rt];
		Update(rt);
		if(t<=mid)return querymin(lson);	
		if(s>mid)return querymin(rson);
		return MIN(querymin(lson),querymin(rson));
	}		
	int querymax(int rt,int l,int r){
		if(s<=l&&t>=r)return Max[rt];
		Update(rt);
		if(t<=mid)return querymax(lson);	
		if(s>mid)return querymax(rson);
		return MAX(querymax(lson),querymax(rson));
	}
	int querysum(int rt,int l,int r){
		if(s<=l&&t>=r)return sum[rt];
		Update(rt);
		if(t<=mid)return querysum(lson);
		if(s>mid)return querysum(rson);	
		return querysum(lson)+querysum(rson);
	}
}T;
int prt[maxn],depth[maxn],_s[maxn],point[maxn];
void Dfs1(int x){
	_s[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(prt[x]==y)continue;
		prt[y]=x;
		depth[y]=depth[x]+1;
		w[y]=e[i].dis;
		point[e[i].num]=y;
		Dfs1(y);
		_s[x]+=_s[y];
	}
}
int pos[maxn],top[maxn],Time;
void Dfs2(int x){
	int hvy=0;
	pos[x]=++Time; 
	T.Q=pos[x];  T.W=w[x];	T.Insert(1,1,n);
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(prt[x]==y)continue;	
		if(_s[hvy]<_s[y])hvy=y;
	}
	if(hvy){
		top[hvy]=top[x];  Dfs2(hvy);
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].to;
			if(prt[x]==y||hvy==y)continue;
			top[y]=y;  Dfs2(y);	
		}
	}
}
void Query_max(int x,int y){
	int ra=top[x],rb=top[y],ans=-Inf;
	while(ra^rb){
		if(depth[ra]<depth[rb]){
			T.s=pos[rb]; T.t=pos[y];
			ans=MAX(ans,T.querymax(1,1,n));
			y=prt[rb];  rb=top[y];	
			
		}	
		else{	
			T.s=pos[ra]; T.t=pos[x];
			ans=MAX(ans,T.querymax(1,1,n));
			x=prt[ra];  ra=top[x];
		}
	}	
	if(x^y){
		if(depth[x]<depth[y]){
			T.s=pos[x]+1,T.t=pos[y];	
		}
		else{
			 T.s=pos[y]+1;  T.t=pos[x];
		}
		ans=MAX(ans,T.querymax(1,1,n));
	}
	printf("%d\n",ans);
}
void Query_min(int x,int y){
	int ra=top[x],rb=top[y],ans=Inf;
	while(ra^rb){
		if(depth[ra]<depth[rb]){
			T.s=pos[rb]; T.t=pos[y];
			ans=MIN(ans,T.querymin(1,1,n));
			y=prt[rb];  rb=top[y];	
			
		}	
		else{	
			T.s=pos[ra]; T.t=pos[x];
			ans=MIN(ans,T.querymin(1,1,n));
			x=prt[ra];  ra=top[x];
		}
	}	
	if(x^y){
		if(depth[x]<depth[y]){
			T.s=pos[x]+1,T.t=pos[y];	
		}
		else{
			 T.s=pos[y]+1;  T.t=pos[x];
		}
		ans=MIN(ans,T.querymin(1,1,n));
	}
	printf("%d\n",ans);
}
void Query_sum(int x,int y){
	int ra=top[x],rb=top[y],ans=0;
	while(ra^rb){
		if(depth[ra]<depth[rb]){
			T.s=pos[rb]; T.t=pos[y];
			ans+=T.querysum(1,1,n);
			y=prt[rb];  rb=top[y];	
			
		}	
		else{	
			T.s=pos[ra]; T.t=pos[x];
			ans+=T.querysum(1,1,n);
			x=prt[ra];  ra=top[x];
		}
	}	
	if(x^y){
		if(depth[x]<depth[y]){
			T.s=pos[x]+1,T.t=pos[y];	
		}
		else{
			 T.s=pos[y]+1;  T.t=pos[x];
		}
		ans+=T.querysum(1,1,n);
	}
	printf("%d\n",ans);
}
void Negate(int x,int y){
	int ra=top[x],rb=top[y];
	while(ra^rb){
		if(depth[ra]<depth[rb]){
			T.s=pos[rb]; T.t=pos[y];
			T.negate(1,1,n);
			y=prt[rb];  rb=top[y];	
		}	
		else{
			T.s=pos[ra]; T.t=pos[x];
			T.negate(1,1,n);
			x=prt[ra];  ra=top[x];	
		}
	}	
	if(x^y){	
		if(depth[x]<depth[y]){
			T.s=pos[x]+1,T.t=pos[y];
		}
		else{
			T.s=pos[y]+1;  T.t=pos[x];
		}
		T.negate(1,1,n);	
	}
}
int main(){
	freopen("nt2011_travel.in","r",stdin);freopen("nt2011_travel.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y,z;  scanf("%d%d%d",&x,&y,&z);	
		Addedge(x+1,y+1,z,i); Addedge(y+1,x+1,z,i);
	}
	depth[1]=1; Dfs1(1);
	top[1]=1;   Dfs2(1);
	int m; scanf("%d",&m);
	char ch[10];
	for(int i=1;i<=m;i++){
		scanf("%s",ch);
		int x,y;  scanf("%d%d",&x,&y);
		if(ch[0]!='C'){x++,y++;}
		if(ch[0]=='C'){
			T.Q=pos[point[x]];  T.W=y;
			T.Insert(1,1,n);
		}if(ch[1]=='A'){
			Query_max(x,y);	
		}if(ch[1]=='I'){
			Query_min(x,y);	
		}if(ch[0]=='S'){
			Query_sum(x,y);	
		}
		if(ch[0]=='N'){
			Negate(x,y);	
		}
	}
	//system("pause");
	return 0;	
}