【BZOJ1036】树的统计

    裸的树链剖分。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=30010,inf=~0U>>1;

struct Segment_Tree
{
	#define ls (o<<1)
	#define rs ((o<<1)|1)
	#define mid ((l+r)>>1)
	int sum[maxn<<2],maxv[maxn<<2];
	int tag[maxn<<2],tagv[maxn<<2];
	int n;
	int a,b,v;

	void Update(int o)
	{
		sum[o]=sum[ls]+sum[rs];
		maxv[o]=max(maxv[ls],maxv[rs]);
	}

	void Mark(int o,int l,int r,int markv)
	{
		sum[o]=markv*(r-l+1);
		maxv[o]=markv;
	}

	void Push_Down(int o,int l,int r)
	{
		if (l==r || !tag[o]) return;
		Mark(ls,l,mid,tagv[o]);
		Mark(rs,mid+1,r,tagv[o]);
		tag[ls]=tag[r]=1;
		tagv[ls]=tagv[rs]=tagv[o];
		tagv[o]=tag[o]=0;
	}

	void Build(int o,int l,int r,int *a)
	{
		if (l==r) {sum[o]=maxv[o]=a[l];return;}
		Build(ls,l,mid,a);
		Build(rs,mid+1,r,a);
		Update(o);
	}

	void Change(int o,int l,int r)
	{
		if (l>=a && r<=b) {Mark(o,l,r,v);tag[o]=1;tagv[o]=v;return;}
		Push_Down(o,l,r);
		if (a<=mid) Change(ls,l,mid);
		if (b>mid)  Change(rs,mid+1,r);
		Update(o);
	}

	int Query_Max(int o,int l,int r)
	{
		if (l>=a && r<=b) return maxv[o];
		Push_Down(o,l,r);
		int res=-inf;
		if (a<=mid) res=max(res,Query_Max(ls,l,mid));
		if (b>mid)  res=max(res,Query_Max(rs,mid+1,r));
		Update(o);
		return res;
	}

	int Query_Sum(int o,int l,int r)
	{
		if (l>=a && r<=b) return sum[o];
		Push_Down(o,l,r);
		int res=0;
		if (a<=mid) res+=Query_Sum(ls,l,mid);
		if (b>mid)  res+=Query_Sum(rs,mid+1,r);
		Update(o);
		return res;
	}
	
	void Change(int x,int _v) {a=b=x;v=_v;Change(1,1,n);}
	int Query_Max(int _a,int _b) {a=_a;b=_b;return Query_Max(1,1,n);}
	int Query_Sum(int _a,int _b) {a=_a;b=_b;return Query_Sum(1,1,n);}
	#undef ls
	#undef rs
	#undef mid
}ST;

struct Tree
{
	int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt;
	int top[maxn],fa[maxn],dep[maxn];
	int wson[maxn],id[maxn],ids;
	int temp[maxn];

	void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}

	int DFS1(int x,int father,int depth)
	{
		int sons=0,maxsons=0;
		fa[x]=father;dep[x]=depth;
		for (int i=head[x];i;i=next[i]) if (E[i]!=father)
		{
			int tsons=DFS1(E[i],x,depth+1);
			sons+=tsons;
			if (tsons>maxsons) maxsons=tsons,wson[x]=E[i];
		}
		return sons+1;
	}

	void DFS2(int x,int is_wson)
	{
		id[x]=++ids;
		if (is_wson==1) top[x]=top[fa[x]];else top[x]=x;
		if (wson[x]) DFS2(wson[x],1);
		for (int i=head[x];i;i=next[i]) if (E[i]!=fa[x] && E[i]!=wson[x]) DFS2(E[i],0);
	}

	void Build(int *a,int n)
	{
		(void)DFS1(1,0,1);
		DFS2(1,0);
		for (int i=1;i<=n;i++) temp[id[i]]=a[i];
		ST.n=n;
		ST.Build(1,1,n,temp);
	}

	void Change(int x,int y) {ST.Change(id[x],y);}
	
	int Query_Max(int x,int y)
	{
		int res=-inf;
		while (top[x]!=top[y])
		{
			int fx=top[x],fy=top[y];
			if (dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
			if (top[x]==x) res=max(res,ST.Query_Max(id[x],id[x])),x=fa[x];
			else res=max(res,ST.Query_Max(id[top[x]],id[x])),x=top[x];
		}
		if (dep[x]>dep[y]) swap(x,y);
		res=max(res,ST.Query_Max(id[x],id[y]));
		return res;
	}

	int Query_Sum(int x,int y)
	{
		int res=0,cx=0,cy=0;
		while (top[x]!=top[y])
		{
			int fx=top[x],fy=top[y];
			if (dep[fx]<dep[fy]) swap(x,y),swap(fx,fy),swap(cx,cy);
			if (top[x]==x)
			{
				if (!cx) res+=ST.Query_Sum(id[x],id[x]);
				cx=0;
				x=fa[x];
			}
			else
			{
				res+=ST.Query_Sum(id[top[x]],(cx?id[fa[x]]:id[x]));
				cx=1;
				x=top[x];
			}
		}
		if (dep[x]>dep[y]) swap(x,y),swap(cx,cy);
		res+=ST.Query_Sum(id[x],id[y]);
		if (cx) res-=ST.Query_Sum(id[x],id[x]);
		if (cy) res-=ST.Query_Sum(id[y],id[y]);
		return res;
	}
}T;

void read(int &x) {char ch=' ';int f=1;while (((ch=getchar())<'0' || ch>'9') && ch!='-');if (ch=='-') f=-1,x=0;else x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';x*=f;}

int a[maxn];
int n,q;

int main()
{
	read(n);
	for (int i=1,x,y;i<n;i++) read(x),read(y),T.Add_Edge(x,y);
	for (int i=1;i<=n;i++) read(a[i]);
	T.Build(a,n);
	read(q);
	while (q--)
	{
		static char cor[10];
		static int x,y;
		scanf("%s",cor);
		read(x),read(y);
		if (cor[0]=='C') T.Change(x,y);
		else if (cor[1]=='M') printf("%d\n",T.Query_Max(x,y));
		else printf("%d\n",T.Query_Sum(x,y));
	}
	return 0;
}