记录编号	307695	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	1.707 s
提交时间	2016-09-16 08:29:27	内存使用	2.50 MiB

#include<cstdio>
using namespace std;
inline void read(int &x)
{
	char ch;bool flag=false;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')flag=1;
	x=ch^'0';
	while(ch=getchar(),ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^'0');
	if(flag) x=-x;
}
//===============================================================
const int Size=30010,INF=-0x7ffffff;
int son[Size],top[Size],dep[Size],tid[Size],rank[Size],fa[Size],siz[Size],tn;
int to[Size<<1],next[Size<<1],head[Size],val[Size],num;
struct Tree{
	int max,sum;
	Tree(){max=INF,sum=0;}
}tree[Size<<2];
inline void Add(int u,int v)
{
	to[++num]=v,next[num]=head[u],head[u]=num;
}
void dfs1(int u,int f,int d)
{
	son[u]=0,siz[u]=1,fa[u]=f,dep[u]=d;
	for(int i=head[u];i;i=next[i]){
		int v=to[i];
		if(v==f) continue;
		dfs1(v,u,d+1);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp,tid[u]=++tn,rank[tid[u]]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int i=head[u];i;i=next[i])
		if(to[i]!=son[u]&&to[i]!=fa[u])
			dfs2(to[i],to[i]);
}
inline int Max(int x,int y){return x>y?x:y;}
inline void pushup(int rt)
{
	tree[rt].max=Max(tree[rt<<1].max,tree[rt<<1|1].max);
	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void build(int l,int r,int rt)
{
	if(l>r) return ;
	if(l==r){
		tree[rt].max=tree[rt].sum=val[rank[l]];
		return ;
	}
	int mid=l+r>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void update(int p,int x,int l,int r,int rt)
{
	if(l>r) return ;
	if(l==r){
		tree[rt].max=tree[rt].sum=x;
		return ;
	}
	int mid=l+r>>1;
	if(mid>=p) update(p,x,l,mid,rt<<1);
	else update(p,x,mid+1,r,rt<<1|1);
	pushup(rt);
}
int query_max(int L,int R,int l,int r,int rt)
{
	if(L>R||l>r) return INF;
	if(l>=L&&r<=R) return tree[rt].max;
	int mid=r+l>>1,ret=INF;
	if(mid>=L) ret=Max(ret,query_max(L,R,l,mid,rt<<1));
	if(mid<R) ret=Max(ret,query_max(L,R,mid+1,r,rt<<1|1));
	return ret;
}
int query_sum(int L,int R,int l,int r,int rt)
{
	if(L>R||l>r) return 0;
	if(l>=L&&r<=R) return tree[rt].sum;
	int mid=r+l>>1,ret=0;
	if(mid>=L) ret+=query_sum(L,R,l,mid,rt<<1);
	if(mid<R) ret+=query_sum(L,R,mid+1,r,rt<<1|1);
	return ret;
}
inline void swap(int& x,int& y){x^=y,y^=x,x^=y;}
int findmax(int u,int v)
{
	int ret=INF;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ret=Max(ret,query_max(tid[top[u]],tid[u],1,tn,1));
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	ret=Max(ret,query_max(tid[u],tid[v],1,tn,1));
	return ret;
}
int findsum(int u,int v)
{
	int ret=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ret+=query_sum(tid[top[u]],tid[u],1,tn,1);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	ret+=query_sum(tid[u],tid[v],1,tn,1);
	return ret;
}
int _521()
{
#define COGS
#ifdef COGS
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
#else
	freopen("1.in","r",stdin);
#endif
	int n,i,q;
	read(n);
	for(i=1;i<n;i++){
		int u,v;
		read(u),read(v);
		Add(u,v),Add(v,u);
	}
	for(i=1;i<=n;i++) read(val[i]);
	dfs1(1,0,1),dfs2(1,1);
	build(1,tn,1);
	read(q);
	for(i=1;i<=q;i++){
		char ch[10];
		int a,b;
		scanf("%s",ch),read(a),read(b);
		if(ch[0]=='Q'){
			if(ch[1]=='M') printf("%d\n",findmax(a,b));
			else printf("%d\n",findsum(a,b));
		}
		else update(tid[a],b,1,tn,1);
	}
	return 0;
}
int _520=_521();
int main(){;}