树剖+树状数组

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],x,y,head[100005],cnt0=0,b[100005],c[100005],d[100005],e[100005],cnt=0,f[100005],g[100005],h[100005],aa[400005][2],ans;
string s;
struct node
{
	int next,to;
} edge[200005];
void add(int from,int to)
{
	edge[++cnt0]=(node){head[from],to};
	head[from]=cnt0;
}
void dfs1(int x,int f)
{
	int y,maxn=0;
	b[x]=f;
	c[x]=c[f]+1;
	d[x]=1;
	for (int i=head[x];i;i=edge[i].next)
	{
		y=edge[i].to;
		if (y!=f)
		{
			dfs1(y,x);
			d[x]+=d[y];
			if (d[y]>maxn)
			{
				maxn=d[y];
				e[x]=y;
			}
		}
	}
}
void dfs2(int x,int t)
{
	int y;
	f[x]=++cnt;
	g[cnt]=a[x];
	h[x]=t;
	if (e[x])
	{
		dfs2(e[x],t);
		for (int i=head[x];i;i=edge[i].next)
		{
			y=edge[i].to;
			if (y!=b[x] && y!=e[x])
			dfs2(y,y);
		}
	}
}
void modify(int x,int y)
{
	int xx=x,z=y-g[x];
	g[x]=y;
	while (xx<=n)
	{
		aa[xx][0]+=z;
		xx+=xx&-xx;
	}
	xx=x;
	while (xx<=n)
	{
		if (y>aa[xx][1])
		aa[x][1]=y;
		else
		return;
		xx+=xx&-xx;
	}
}
int query1(int x)
{
	int result=0;
	while (x)
	{
		result+=aa[x][0];
		x-=x&-x;
	}
	return result;
}
int query2(int x,int y)
{
	int result=-0x80000000;
	while (y>=x)
	{
		if (y-(y&-y)>x)
		{
			result=max(result,aa[y][1]);
			y-=y&-y;
		}
		else
		{
			result=max(result,g[y]);
			--y;
		}
	}
	return result;
}
int main()
{
	cin>>n;
	for (int i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for (int i=1;i<=n;++i)
	scanf("%d",&a[i]);
	dfs1(1,0);
	dfs2(1,1);
	for (int i=1;i<=n;++i)
	modify(i,g[i]);
	cin>>m;
	while (m--)
	{
		cin>>s;
		if (s=="CHANGE")
		{
			scanf("%d%d",&x,&y);
			modify(f[x],y);
		}
		else if (s=="QSUM")
		{
			scanf("%d%d",&x,&y);
			ans=0;
			while (h[x]!=h[y])
			{
				if (c[h[x]]<c[h[y]])
				swap(x,y);
				ans+=query1(f[x])-query1(f[h[x]]-1);
				x=b[h[x]];
			}
			if (c[x]>c[y])
			swap(x,y);
			ans+=query1(f[y])-query1(f[x]-1);
			cout<<ans<<'\n';
		}
		else
		{
			scanf("%d%d",&x,&y);
			ans=-0x80000000;
			while (h[x]!=h[y])
			{
				if (c[h[x]]<c[h[y]])
				swap(x,y);
				ans=max(ans,query2(f[h[x]],f[x]));
				x=b[h[x]];
			}
			if (c[x]>c[y])
			swap(x,y);
			ans=max(ans,query2(f[x],f[y]));
			cout<<ans<<'\n';
		}
	}
}