记录编号	318311	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	1.116 s
提交时间	2016-10-09 08:15:17	内存使用	86.15 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1500100
using namespace std;
int top[maxn],size[maxn],deep[maxn],fa[maxn],son[maxn];
int dfn[maxn],timark,dfst[maxn],value[maxn];
int maxnum[maxn],sumnum[maxn];
int head[maxn],tot,qx,qy,maxx,ans;
int n,m,x,y;
struct Edge{
	int to,next;
}edge[maxn<<1];
void Addedge(int x,int y){
	edge[++tot].to=y;
	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])
		{
			fa[p] = x ;
			deep[p] = deep[x] + 1;
			dfs1(p);
			size[x] += size[p] ;
			if(size[p] > size[ son[x] ] )son[x] = p ;
		}
	}
}
void dfs2(int x,int tp)
{
	top[x] = tp ;
	dfn[x] = ++ timark ;
	dfst[ timark ] = x; 
	if(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 Build(int rt, int l ,int r)
{
	if(l == r )
	{
		maxnum[rt] = sumnum[rt] = value[ dfst[l] ];
		return;
	}
	int mid = ( l + r ) >> 1;
	Build(rt<<1,l,mid);
	Build(rt<<1|1,mid+1,r);
	maxnum[rt] = max ( maxnum[rt<<1] , maxnum[rt<<1|1] );
	sumnum[rt] = sumnum[rt<<1] + sumnum[rt<<1|1] ;
}
void Change(int rt,int l,int r,int x,int y)
{
	if( l == r )
	{
		maxnum[rt] = sumnum[rt] = y ;
		return ;
	}
	int mid = ( l + r ) >> 1; 
	if(x <= mid ) Change(rt<<1,l,mid,x,y);
	if( x > mid ) Change(rt<<1|1,mid+1,r,x,y);
	maxnum[rt] = max ( maxnum[rt<<1] , maxnum[rt<<1|1] );
	sumnum[rt] = sumnum[rt<<1] + sumnum[rt<<1|1] ;
}
void get_max(int rt,int l,int r)
{
	if( qx <= l && qy >= r )
	{
		maxx = max ( maxx , maxnum[rt] );
		return ;
	}
	int mid = ( l + r ) >> 1; 
	if(qx <= mid )get_max(rt<<1,l,mid);
	if(qy > mid )get_max(rt<<1|1,mid+1,r);
}
void get_sum(int rt,int l,int r)
{
	if( qx <= l && qy >= r )
	{
		ans += sumnum[rt] ;
		return ;
	}
	int mid = ( l + r ) >> 1; 
	if(qx <= mid )get_sum(rt<<1,l,mid);
	if(qy > mid )get_sum(rt<<1|1,mid+1,r);
}
int query_sum(int x,int y)
{
	int fx = top[x] , fy = top[y] ;
	int ret = 0 ;
	while( fx != fy )
	{
		if(deep[fx] < deep[fy] )
		{
			swap(x,y);
			swap(fx,fy);
		}
		qx = dfn[fx] ;
		qy = dfn[x] ;
		ans = 0 ;
		get_sum(1,1,n);
		ret += ans ;
		x = fa[fx] ;
		fx = top[x] ;
	}
	if( deep[x] > deep[y] )swap(x,y);
	qx = dfn[x] ;
	qy = dfn[y] ;
	ans = 0 ;
	get_sum(1,1,n);
	ret += ans ;
	return ret;
}
int query_max(int x,int y)
{
	int fx = top[x] , fy = top[y] ;
	int ret = -0x7f7f7f7f ;
	while( fx != fy )
	{
		if(deep[fx] < deep[fy] )
		{
			swap(x,y);
			swap(fx,fy);
		}
		qx = dfn[fx] ;
		qy = dfn[x] ;
		maxx = -0x7f7f7f7f ;
		get_max(1,1,n);
		ret = max ( maxx , ret );
		x = fa[fx] ;
		fx = top[x] ;
	}
	if( deep[x] > deep[y] )swap(x,y);
	qx = dfn[x] ;
	qy = dfn[y] ;
	maxx = -0x7f7f7f7f ;
	get_max(1,1,n);
	ret = max ( maxx , ret );
	return ret;
}
int main()
{
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout); 
	scanf("%d",&n);
	for(int i = 1 ; i < n ; ++ i )
	{
		scanf("%d %d",&x,&y);
		Addedge(x,y);Addedge(y,x);
	}
	for(int i = 1 ; i <= n ; ++ i )
	{
		scanf("%d", &value[i] );
	}
	dfs1(1);
	dfs2(1,1);
	Build(1,1,n);
	scanf("%d",&m);
	char op[10];
	while( m -- )
	{
		scanf("%s",op);
		if(op[0] == 'Q')
		{
			scanf("%d %d",&x,&y);
			if(op[1] == 'M' )
			{
				printf("%d\n",query_max(x,y));
			}
			else printf("%d\n",query_sum(x,y));
		}
		else
		{
			scanf("%d %d",&x,&y);
			Change(1,1,n,dfn[x],y);
		}
	}
//	system("pause");
}