题解
这真的只是一道模板题：一个树链剖分套上一个线段树（令我窒息的组合）。
既然是模板题，那就直接上代码吧。
代码
#include<bits/stdc++.h>
#define N 30000
using namespace std;
int n,ee=0,tot=0,a[N+5],lnk[N+5],fa[N+5],Size[N+5],Depth[N+5],Wson[N+5],Top[N+5],Pos[N+5],Num[N+5];
int Sum[N<<2],Max[N<<2];
struct edge
{
int to,nxt;
}e[2*N+5];
inline char tc()
{
static char ff[100000],*A=ff,*B=ff;
return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0;int f=1;char ch;
while(!isdigit(ch=tc())) if(ch=='-') f=-1;
while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
x*=f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void read_string(string &st)
{
st="";char ch;
while((ch=tc())<'A'||ch>'Z');
while(st+=ch,(ch=tc())>='A'&&ch<='Z');
}
inline void add(int x,int y)
{
e[++ee]=(edge){y,lnk[x]},lnk[x]=ee;
}
inline void dfs1(int x)//第一遍DFS，预处理出每个节点的父亲、深度、重儿子以及子树大小
{
register int i;Size[x]=1;
for(i=lnk[x];i;i=e[i].nxt)
if(e[i].to^fa[x]) fa[e[i].to]=x,Depth[e[i].to]=Depth[x]+1,dfs1(e[i].to),Size[x]+=Size[e[i].to],(Size[e[i].to]>Size[Wson[x]]?Wson[x]=e[i].to:0);
}
inline void dfs2(int x,int tp)//第二遍DFS，根据先前预处理出的重儿子，剖分出轻重链
{
register int i;Top[Num[Pos[x]=++tot]=x]=tp;
if(Wson[x]) dfs2(Wson[x],tp);
for(i=lnk[x];i;i=e[i].nxt)
if(e[i].to!=fa[x]&&e[i].to!=Wson[x]) dfs2(e[i].to,e[i].to);
}
inline void PushUp(int rt)
{
Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1],Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
inline void Build(int l,int r,int rt)//一个朴素的建树过程
{
if(l==r)
{
Sum[rt]=Max[rt]=a[Num[l]];
return;
}
int mid=l+r>>1;
Build(l,mid,rt<<1),Build(mid+1,r,rt<<1|1),PushUp(rt);
}
inline void Update(int l,int r,int rt,int x,int v)//单点修改
{
if(l==r)
{
Sum[rt]=Max[rt]=v;
return;
}
int mid=l+r>>1;
(mid>=x?Update(l,mid,rt<<1,x,v):Update(mid+1,r,rt<<1|1,x,v)),PushUp(rt);
}
inline int Query_Max(int l,int r,int rt,int L,int R)//查询区间最大值
{
if(L>R) L^=R,R^=L,L^=R;
if(L<=l&&r<=R) return Max[rt];
int mid=l+r>>1,res=-1e9;
if(L<=mid) res=max(res,Query_Max(l,mid,rt<<1,L,R));
if(R>mid) res=max(res,Query_Max(mid+1,r,rt<<1|1,L,R));
return res;
}
inline int Query_Sum(int l,int r,int rt,int L,int R)//查询区间和
{
if(L>R) L^=R,R^=L,L^=R;
if(L<=l&&r<=R) return Sum[rt];
int mid=l+r>>1,res=0;
if(L<=mid) res+=Query_Sum(l,mid,rt<<1,L,R);
if(R>mid) res+=Query_Sum(mid+1,r,rt<<1|1,L,R);
return res;
}
inline int Qmax(int s1,int s2)//对数据进行处理，并调用线段树的Query_Max()函数来求出答案
{
int res=-1e9;
while(Top[s1]^Top[s2])
{
if(Depth[Top[s1]]<Depth[Top[s2]]) s1^=s2,s2^=s1,s1^=s2;
res=max(res,Query_Max(1,n,1,Pos[Top[s1]],Pos[s1])),s1=fa[Top[s1]];
}
if(Depth[s1]<Depth[s2]) s1^=s2,s2^=s1,s1^=s2;
return max(res,Query_Max(1,n,1,Pos[s1],Pos[s2]));
}
inline int Qsum(int s1,int s2)//对数据进行处理，并调用线段树的Query_Sum()函数来求出答案
{
int res=0;
while(Top[s1]^Top[s2])
{
if(Depth[Top[s1]]<Depth[Top[s2]]) s1^=s2,s2^=s1,s1^=s2;
res+=Query_Sum(1,n,1,Pos[Top[s1]],Pos[s1]),s1=fa[Top[s1]];
}
if(Depth[s1]<Depth[s2]) s1^=s2,s2^=s1,s1^=s2;
return res+Query_Sum(1,n,1,Pos[s1],Pos[s2]);
}
int main()
{
freopen("a.in","r",stdin);
register int i;int x,y;
for(read(n),i=1;i<n;++i)
read(x),read(y),add(x,y),add(y,x);
for(i=1;i<=n;++i)
read(a[i]);
dfs1(1),dfs2(1,1),Build(1,n,1);
int Q;read(Q);
while(Q--)
{
string st;
read_string(st),read(x),read(y);
if(st=="CHANGE") Update(1,n,1,Pos[x],y);
else if(st=="QMAX") write(Qmax(x,y)),putchar('
');
else if(st=="QSUM") write(Qsum(x,y)),putchar('
');
}
return 0;
}