记录编号	157006	评测结果	AAAAAAAAAA
题目名称	[国家集训队2011]旅游	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.172 s
提交时间	2015-04-07 07:06:03	内存使用	4.70 MiB

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100010,inf=0x7fffffff;
int c[maxn][2],fa[maxn],sum[maxn],mmax[maxn],mmin[maxn];
int tot,val[maxn],bel[maxn];
struct edge{int to,id,val;};
bool neg[maxn],vis[maxn];
vector <edge> g[maxn];
char str[10];
bool isrt(int x){
	return (!fa[x])||(c[fa[x]][0]!=x&&c[fa[x]][1]!=x);
}
void update(int x){
	sum[x]=sum[c[x][0]]+sum[c[x][1]]+val[x];
	mmax[x]=max(val[x],max(mmax[c[x][0]],mmax[c[x][1]]));
	mmin[x]=min(val[x],min(mmin[c[x][0]],mmin[c[x][1]]));
}
void negate(int x){
	if(!x) return;
	val[x]=-val[x],sum[x]=-sum[x];
	neg[x]^=1,swap(mmax[x],mmin[x]);
	mmax[x]=-mmax[x],mmin[x]=-mmin[x];
}
void pushdown(int u){
	if(!u||!neg[u]) return;
	negate(c[u][0]),negate(c[u][1]),neg[u]=0;
}
void rot(int x,bool d){
	int y=fa[x],z=fa[y];
	if(c[z][0]==y) c[z][0]=x;
	else if(c[z][1]==y) c[z][1]=x;
	fa[x]=z,fa[c[x][d]]=y,c[y][!d]=c[x][d],c[x][d]=y,fa[y]=x;
	update(y);
}
void splay(int x){
	pushdown(x);
	while(!isrt(x))
		pushdown(fa[x]),pushdown(x),rot(x,c[fa[x]][0]==x);
	update(x);
}
void access(int u){
	for(int v=0;u;u=fa[u])
		splay(u),c[u][1]=v,v=u,update(u);
}
#define p g[x][i]
void dfs(int x){
	vis[x]=1;
	for(int i=g[x].size()-1;~i;i--)
		if(!vis[p.to])
			fa[p.to]=x,bel[p.id>>1]=p.to,val[p.to]=p.val,dfs(p.to);
}
void query(int u,int v){
	access(v);
	for(v=0;u;u=fa[u]){
		splay(u);
		if(!fa[u]){
			if(str[0]=='N') negate(v),negate(c[u][1]);
			else if(str[0]=='S') printf("%d\n",sum[v]+sum[c[u][1]]);
			else if(str[1]=='A') printf("%d\n",max(mmax[v],mmax[c[u][1]]));
			else printf("%d\n",min(mmin[v],mmin[c[u][1]]));
			return;
		}
		c[u][1]=v,v=u,update(u);
	}
}
int main(){
	freopen("nt2011_travel.in" ,"r",stdin ) ;
    freopen("nt2011_travel.out","w",stdout) ;
	int n,m,u,v,k;
	scanf("%d",&n),tot=1;
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&u,&v,&k),u++,v++;
		g[u].push_back((edge){v,++tot,k});
		g[v].push_back((edge){u,++tot,k});
	}
	dfs(1),mmax[0]=-inf,mmin[0]=inf;
	scanf("%d",&m);
	while(m--){
		scanf("%s%d%d",str,&u,&v);
		if(str[0]=='C') u=bel[u],splay(u),val[u]=v,update(u);
		else query(++u,++v);
	}
}