树链剖分模板题

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define int long long
#define INF 0x3f3f3f3f
#define endl '\n'
using namespace std;
int const N=400000;
int n;
int fa[N],d[N],siz[N],son[N],top[N],cntt=0,pre[N];
int dfn[N];
int w[N];
int laz[N<<2];
struct Tree
{
	int sum,maxn;
}t[N<<2];
struct node
{
	int next,to;
}q[N*2];
int head[N],cnt=0;
void add(int u,int v)
{
	q[++cnt].to=v;
	q[cnt].next=head[u];
	head[u]=cnt;
}
void pushup(int p)
{
	t[p].maxn=max(t[lc].maxn,t[rc].maxn);
	t[p].sum=t[lc].sum+t[rc].sum;
}
void build(int p,int l,int r)
{
	if(l==r)
	{
		//cout<<l<<" "<<pre[l]<<endl;
		t[p].sum=t[p].maxn=w[pre[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p);
}
/*
void pushdown(int p,int l,int r)
{
	int mid=(l+r)>>1;
	t[lc].maxn+=laz[p];
	t[lc].sum+=(mid-l+1)*laz[p];
	t[rc].maxn+=laz[p];
	t[rc].sum+=(r-mid)*laz[p];
	laz[lc]+=laz[p];
	laz[rc]+=laz[p];
	laz[p]=0; 
}*/
int queryma(int p,int l,int r,int x,int y)
{
	if(l>=x&&r<=y) return t[p].maxn;
	//pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(y<=mid) return queryma(lc,l,mid,x,y);
	else if(x>mid) return queryma(rc,mid+1,r,x,y);
	else return max(queryma(lc,l,mid,x,y),queryma(rc,mid+1,r,x,y));
}
int querysum(int p,int l,int r,int x,int y)
{
	if(l>=x&&r<=y) return t[p].sum;
//	pushdown(p,l,r);
	int ans=0;
	int mid=(l+r)>>1;
	if(x<=mid) ans+=querysum(lc,l,mid,x,y);
	if(y>mid) ans+=querysum(rc,mid+1,r,x,y);
	return ans;
}
void update(int p,int l,int r,int x,int val)
{
	if(l==r)
	{
		t[p].maxn=val;
		t[p].sum=val;
		return;
	} 
	int mid=(l+r)>>1;
	if(x<=mid) update(lc,l,mid,x,val);
	if(x>mid) update(rc,mid+1,r,x,val);
	pushup(p);
}
int query_ansmax(int x,int y)
{
	int maxx=-INF;
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		maxx=max(maxx,queryma(1,1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	int left=dfn[x],right=dfn[y];
	if(left>right) swap(left,right);
	maxx=max(maxx,queryma(1,1,n,left,right));
	return maxx;
}
int query_anssum(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		ans+=querysum(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	int left=dfn[x],right=dfn[y];
	ans+=querysum(1,1,n,left,right);
	return ans;
}
int dfs1(int u)
{
	son[u]=-1;
	siz[u]=1;
	d[u]=d[fa[u]]+1;
	for(int i=head[u];i;i=q[i].next)
	{
		int v=q[i].to;
		if(d[v]!=0) continue;
		fa[v]=u;
		siz[u]+=dfs1(v);
		if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
	}
	return siz[u];
}
void dfs2(int u,int t)
{
	//cout<<u<<endl;
	dfn[u]=++cntt;
	top[u]=t;
	pre[cntt]=u;
	if(son[u]!=-1) dfs2(son[u],t);
	for(int i=head[u];i;i=q[i].next)
	{
		int v=q[i].to;
		if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int m;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++) cin>>w[i];
	cin>>m;
	int size=dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	while(m--)
	{
		string opt;
		cin>>opt;
		if(opt=="QMAX")
		{
			int x,y;
			cin>>x>>y;
			cout<<query_ansmax(x,y)<<endl;
		}
		else if(opt=="QSUM")
		{
			int x,y;
			cin>>x>>y;
			cout<<query_anssum(x,y)<<endl;
		}
		else if(opt=="CHANGE")
		{
			int x,d;
			cin>>x>>d;
			update(1,1,n,dfn[x],d);
		}
	}
	return 0;
}