记录编号	458344	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	1.218 s
提交时间	2017-10-11 07:41:09	内存使用	2.49 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
	return x*f;
}
const int maxn=30010;
int n,m;
vector<int>t[maxn];
int val[maxn],sz[maxn],dep[maxn],fa[maxn],top[maxn],id[maxn],pre[maxn],son[maxn],tot;
inline void dfs1(int u,int f,int d){
	sz[u]=1;fa[u]=f;dep[u]=d;
	for(int i=0;i<(int)t[u].size();i++){
		int v=t[u][i];
		if(v==f)continue;
		dfs1(v,u,d+1);
		sz[u]+=sz[v];
		if(!son[u]||sz[son[u]]<sz[v])son[u]=v;
	}
}
inline void dfs2(int u,int tou){
	top[u]=tou;id[u]=++tot;pre[tot]=u;
	if(!son[u])return ;
	dfs2(son[u],tou);
	for(int i=0;i<(int)t[u].size();i++){
		int v=t[u][i];
		if(v!=fa[u]&&v!=son[u])dfs2(v,v);
	}
}
int sum[maxn<<2],maxx[maxn<<2];
inline void build(int o,int l,int r){
	if(l==r){
		sum[o]=val[pre[l]];
		maxx[o]=val[pre[l]];
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	build(ls,l,m);
	build(rs,m+1,r);
	sum[o]=sum[ls]+sum[rs];
	maxx[o]=max(maxx[ls],maxx[rs]);
}
inline void change(int o,int l,int r,int nl,int nr,int v){
	if(l>=nl&&r<=nr){
		sum[o]=v;
		maxx[o]=v;
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(m>=nl)change(ls,l,m,nl,nr,v);
	if(m<nr)change(rs,m+1,r,nl,nr,v);
	sum[o]=sum[ls]+sum[rs];
	maxx[o]=max(maxx[ls],maxx[rs]);
}
inline int findsum(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr)return sum[o];
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	int ans=0;
	if(m>=nl)ans+=findsum(ls,l,m,nl,nr);
	if(m<nr)ans+=findsum(rs,m+1,r,nl,nr);
	return ans;
}
char ru[10];
inline int findmax(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr)return maxx[o];
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	int ans=-0x7fffffff;
	if(m>=nl)ans=max(ans,findmax(ls,l,m,nl,nr));
	if(m<nr)ans=max(ans,findmax(rs,m+1,r,nl,nr));
	return ans;
}
inline void gsum(int x,int y){
	int u=top[x],v=top[y];
	int ans=0;
	while(u!=v){
		if(dep[u]<dep[v])swap(u,v),swap(x,y);
		ans+=findsum(1,1,n,id[u],id[x]);
		x=fa[u],u=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	ans+=findsum(1,1,n,id[x],id[y]);
	printf("%d\n",ans);
}
inline void gmax(int x,int y){
	int u=top[x],v=top[y];
	int ans=-0x7fffffff;
	while(u!=v){
		if(dep[u]<dep[v])swap(u,v),swap(x,y);
		ans=max(ans,findmax(1,1,n,id[u],id[x]));
		x=fa[u],u=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	ans=max(ans,findmax(1,1,n,id[x],id[y]));
	printf("%d\n",ans);
}
int main(){
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		t[u].push_back(v);
		t[v].push_back(u);  
	}
	for(int i=1;i<=n;i++)val[i]=read();
	dfs1(1,0,1);dfs2(1,1);
	build(1,1,n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%s",ru);
		int x,y;
		scanf("%d%d",&x,&y);
		if(ru[1]=='S'){
			gsum(x,y);
		}
		if(ru[1]=='M'){
			gmax(x,y);
		}
		if(ru[1]=='H'){
			change(1,1,n,id[x],id[x],y);
		}
	}
	return 0;
}