记录编号	323786	评测结果	AAAAAAAAAA
题目名称	[国家集训队2011]旅游	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.251 s
提交时间	2016-10-17 07:18:03	内存使用	27.78 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
const int maxn = 100010 << 2 ;
int top[maxn],deep[maxn],fa[maxn],dfn[maxn],size[maxn],son[maxn],pos[maxn],id[maxn],dis[maxn];
int head[maxn],tot,cnt,n,m,k,x,y,z,maxnum[maxn],minnum[maxn],sumnum[maxn],L,R,lazy[maxn];
char ch[10];
struct Edge{
	int to,next,dis,num;
}edge[maxn];
void Addedge(int x,int y,int z,int w){
	edge[++tot].to=y;
	edge[tot].dis=z;
	edge[tot].num=w;
	edge[tot].next=head[x];
	head[x]=tot;
}
void dfs1(int x){
	size[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int p=edge[i].to;
		if(!size[p]){
			deep[p]=deep[x]+1;
			fa[p]=x;
			pos[ edge[i].num ] = p ;
			dis[p] = edge[i].dis;
			dfs1(p);
			size[x] += size[p];
			if(size[son[x]]<size[p])son[x]=p;
		}
	}
}
void dfs2(int x,int tp){
	top[x]=tp;dfn[x]=++cnt;id[cnt]=x;
	if(size[son[x]])dfs2(son[x],tp);
	for(int i=head[x];i;i=edge[i].next){
		int p=edge[i].to;
		if(!dfn[p])dfs2(p,p);
	}
}
void Swap(int &a,int &b){
	int tmp=a;
	a=-b;
	b=-tmp;
}
void Update(int rt){
	if(lazy[rt]){
		Swap(maxnum[rt<<1],minnum[rt<<1]);
		Swap(maxnum[rt<<1|1],minnum[rt<<1|1]);
		sumnum[rt<<1]=-sumnum[rt<<1];
		sumnum[rt<<1|1]=-sumnum[rt<<1|1];
		lazy[rt<<1]=!lazy[rt<<1];
		lazy[rt<<1|1]=!lazy[rt<<1|1];
		lazy[rt]=0;
	}
} 
void Build(int rt,int l,int r){
	if(l==r){
		maxnum[rt] = minnum[rt] = sumnum[rt] =  dis[ id[l] ] ;
		return;
	}
	int mid = (l+r)>>1;
	Build(rt<<1,l,mid);
	Build(rt<<1|1,mid+1,r);
	maxnum[rt]=std::max(maxnum[rt<<1],maxnum[rt<<1|1]);
	minnum[rt]=std::min(minnum[rt<<1],minnum[rt<<1|1]);
	sumnum[rt]=sumnum[rt<<1]+sumnum[rt<<1|1];
}
int query_max(int rt,int l,int r){
	if( L <= l && R >= r)return maxnum[rt];
	Update(rt);
	int mid=(l+r)>>1;
	int ans = -0x7f7f7f7f ;
	if(L <= mid )ans = std::max ( ans ,query_max(rt<<1,l,mid));
	if( R > mid ) ans = std::max ( ans ,query_max(rt<<1|1,mid+1,r));
	return ans;
}
int query_min(int rt,int l,int r){
	if( L <= l && R >= r)return minnum[rt];
	Update(rt);
	int mid=(l+r)>>1;
	int ans = 0x7f7f7f7f ;
	if(L <= mid )ans = std::min ( ans ,query_min(rt<<1,l,mid));
	if( R > mid ) ans = std::min ( ans ,query_min(rt<<1|1,mid+1,r));
	return ans;
}
int query_sum(int rt,int l,int r){
	if( L <= l && R >= r)return sumnum[rt];
	Update(rt);
	int mid=(l+r)>>1;
	int ans = 0 ;
	if(L <= mid )ans += query_sum(rt<<1,l,mid);
	if( R > mid ) ans += query_sum(rt<<1|1,mid+1,r);
	return ans;
}
int Query_max(int x,int y){
	int ans = -0x7f7f7f7f ;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])std::swap(x,y);
		L = dfn[top[x]], R = dfn[x] ;
		ans = std::max ( ans , query_max(1,1,n));
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])std::swap(x,y);
	L = dfn[son[x]] , R = dfn[y] ;
	ans = std::max ( ans ,query_max(1,1,n));
	return ans;
}
int Query_min(int x,int y){
	int ans = 0x7f7f7f7f ;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])std::swap(x,y);
		L = dfn[top[x]], R = dfn[x] ;
		ans = std::min ( ans , query_min(1,1,n));
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])std::swap(x,y);
	L = dfn[son[x]] , R = dfn[y] ;
	ans = std::min ( ans ,query_min(1,1,n));
	return ans;
}
int Query_sum(int x,int y){
	int ans = 0 ;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])std::swap(x,y);
		L = dfn[top[x]], R = dfn[x] ;
		ans +=  query_sum(1,1,n);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])std::swap(x,y);
	L = dfn[son[x]] , R = dfn[y] ;
	ans += query_sum(1,1,n);
	return ans;
}
void Insert(int rt,int l,int r,int x,int w){
	if(l==r){maxnum[rt]=minnum[rt]=sumnum[rt]=w;return;}
	Update(rt);
	int mid=(l+r)>>1;
	if(x <= mid)Insert(rt<<1,l,mid,x,w);
	else Insert(rt<<1|1,mid+1,r,x,w);
	maxnum[rt]=std::max(maxnum[rt<<1],maxnum[rt<<1|1]);
	minnum[rt]=std::min(minnum[rt<<1],minnum[rt<<1|1]);
	sumnum[rt]=sumnum[rt<<1]+sumnum[rt<<1|1];
}
void _negate(int rt,int l,int r,int a,int b){
	if(a<=l&&b>=r){
		lazy[rt]=!lazy[rt];
		Swap(minnum[rt],maxnum[rt]);
		sumnum[rt]=-sumnum[rt];
		return;
	}
	Update(rt);
	int mid=(l+r)>>1;
	if(a<=mid)_negate(rt<<1,l,mid,a,b);
	if(b>mid)_negate(rt<<1|1,mid+1,r,a,b);
	maxnum[rt]=std::max(maxnum[rt<<1],maxnum[rt<<1|1]);
	minnum[rt]=std::min(minnum[rt<<1],minnum[rt<<1|1]);
	sumnum[rt]=sumnum[rt<<1]+sumnum[rt<<1|1];
}
void Negate(int x,int y){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])std::swap(x,y);
		_negate(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])std::swap(x,y);
	_negate(1,1,n,dfn[ son[x] ],dfn[y]);
}
int main(){
	freopen("nt2011_travel.in","r",stdin);
	freopen("nt2011_travel.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		++x,++y;
		Addedge(x,y,z,i);
		Addedge(y,x,z,i);
	}
	deep[1]=1;dfs1(1);dfs2(1,1);
	Build(1,1,n);
	scanf("%d",&m);
	while(m--){
		scanf("%s",ch);
		if(ch[0]=='C'){
			scanf("%d%d",&x,&y);
			Insert(1,1,n,dfn[pos[x]],y);
		}
		else if(ch[0]=='S'){
			scanf("%d%d",&x,&y);
			++x,++y;
			printf("%d\n",Query_sum(x,y));
		}
		else if(ch[0]=='M'){
			scanf("%d%d",&x,&y);
			++x,++y;
			if(ch[1]=='I'){
				printf("%d\n",Query_min(x,y));}
			else{
				printf("%d\n",Query_max(x,y));
			}
		}
		else {
			scanf("%d%d",&x,&y);
			++x,++y;
			Negate(x,y);
		}
	}
}