记录编号	270218	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	1.215 s
提交时间	2016-06-14 16:21:01	内存使用	40.37 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>

using namespace std;

int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
const int maxn=500000;

struct edge{
	int to,next;
}e[maxn*2];
int tot,head[maxn];
void add(int u,int v){
	e[++tot].to=v;
	e[tot].next=head[u];
	head[u]=tot;
}
 
int n,le,ri;
int size[maxn],fa[maxn],son[maxn],deep[maxn],dis[maxn],top[maxn],dfs_cnt,dfn[maxn],pos[maxn];
int num[maxn*4],sum[maxn*4];

void dfs1(int u){
	size[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(size[to]) continue;
		deep[to]=deep[u]+1;
		fa[to]=u;
		dfs1(to);
		size[u]+=size[to];
		if(size[son[u]]<size[to]) son[u]=to;
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	dfn[u]=++dfs_cnt;
	pos[dfs_cnt]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(!dfn[to]) dfs2(to,to);
	}
}
void Build(){
	deep[1]=1;
	dfs1(1);
	dfs2(1,1);
}

void build(int rt,int l,int r){
	if(l==r){
		num[rt]=sum[rt]=dis[pos[l]];
		//printf("%d %d %d %d %d\n",rt,l,num[rt],sum[rt],dis[pos[l]]);
		return;
	}
	int mid=(l+r)/2;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	num[rt]=max(num[rt*2],num[rt*2+1]);
	sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void insert(int rt,int l,int r,int k,int w){
	if(l==r){
		num[rt]=sum[rt]=w;
		return;
	}
	int mid=(l+r)/2;
	if(k<=mid) insert(rt*2,l,mid,k,w);
	else insert(rt*2+1,mid+1,r,k,w);
	num[rt]=max(num[rt*2],num[rt*2+1]);
	sum[rt]=sum[rt*2]+sum[rt*2+1];
}
int querymax(int rt,int l,int r){
	if(le<=l&&ri>=r)return num[rt];
	int ans=-0x7f7f7f7f;
	int mid=(l+r)/2;
	if(le<=mid) ans=max(ans,querymax(rt*2,l,mid));
	if(ri>mid)  ans=max(ans,querymax(rt*2+1,mid+1,r));
	return ans;
}
int querymax2(int l,int r){
	le=l,ri=r;
	return querymax(1,1,n);
}
int querymax1(int a,int b){
	int ans=-0x7f7f7f7f;
	while(top[a]!=top[b]){
		if(deep[top[a]]<deep[top[b]]) swap(a,b);
		ans=max(ans,querymax2(dfn[top[a]],dfn[a]));
		a=fa[top[a]];
	}
	if(deep[a]>deep[b]) swap(a,b);
	ans=max(ans,querymax2(dfn[a],dfn[b]));
	return ans; 
}

int querysum(int rt,int l,int r){
	if(le<=l&&ri>=r)return sum[rt];
	int ans=0;
	int mid=(l+r)/2;
	if(le<=mid) ans+=querysum(rt*2,l,mid);
	if(ri>mid)  ans+=querysum(rt*2+1,mid+1,r);
	return ans;
}
int querysum2(int l,int r){
	le=l,ri=r;
	return querysum(1,1,n);
}

int querysum1(int a,int b){
	int ans=0;
	while(top[a]!=top[b]){
		if(deep[top[a]]<deep[top[b]]) swap(a,b);
		ans+=querysum2(dfn[top[a]],dfn[a]);
		a=fa[top[a]];
	}
	if(deep[a]>deep[b]) swap(a,b);
	ans+=querysum2(dfn[a],dfn[b]);
	// 因为此题给的是点权 并不是边权压到点上
	// 所以再求a到b时 LCA 也要加上 
	// dfn[a],dfn[b]   而不是dfn[son[a]],dfn[b] 
	return ans; 
}

int main(){
	freopen("bzoj_1036.in","r",stdin);freopen("bzoj_1036.out","w",stdout);
	n=read();//局部掩盖全局 
	int a,b;
	for(int i=1;i<n;i++){
		a=read(),b=read();
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++) dis[i]=read();
	Build();
	build(1,1,n);
	char ch[6];
	int q=read();
	while(q--){
		scanf("%s",ch);
		a=read(),b=read();
		if(ch[1]=='M') printf("%d\n",querymax1(a,b));
		else if(ch[1]=='S') printf("%d\n",querysum1(a,b));
		else insert(1,1,n,dfn[a],b);
	} 
	fclose(stdin);fclose(stdout);
	return 0;
}