Solution:

就是树链剖分入门题啦~

// luogu-judger-enable-o2#include
    
     #define N 30005#define M 200005#define lson now<<1#define rson now<<1|1#define INF 0x7fffffffusing namespace std;int n,tot,first[N],val[N];int father[N],size[N],maxson[N],depth[N],top[N],id[N],sign,wnew[N];int ans=0;struct Edge{    int to,next;}edge[2*N];inline void addedge(int x,int y){    tot++;    edge[tot].to=y;    edge[tot].next=first[x];    first[x]=tot;}struct node{    int l,r,sum,maxv;}tree[4*N];inline void build(int l,int r,int now){    tree[now].l=l,tree[now].r=r,tree[now].sum=0,tree[now].maxv=0;    if(l==r)    {        tree[now].sum=wnew[l];        tree[now].maxv=wnew[l];        return;    }    int m=(l+r)>>1;    build(l,m,lson);    build(m+1,r,rson);        tree[now].sum=tree[lson].sum+tree[rson].sum;    tree[now].maxv=max(tree[lson].maxv,tree[rson].maxv);}inline void update(int now,int x,int k){    if(tree[now].l==x&&tree[now].r==x)    {        tree[now].sum=k;        tree[now].maxv=k;        return;    }    int m=(tree[now].l+tree[now].r)>>1;    if(x<=m) update(lson,x,k);    else update(rson,x,k);        tree[now].sum=tree[lson].sum+tree[rson].sum;    tree[now].maxv=max(tree[lson].maxv,tree[rson].maxv);}inline void query_sum(int l,int r,int now){    if(l<=tree[now].l&&tree[now].r<=r)     {        ans+=tree[now].sum;        return;    }    int m=(tree[now].l+tree[now].r)>>1;    if(l<=m)    query_sum(l,r,lson);    if(r>m) query_sum(l,r,rson);}inline void query_max(int l,int r,int now){    if(l<=tree[now].l&&tree[now].r<=r)     {        ans=max(ans,tree[now].maxv);        return;    }    int m=(tree[now].l+tree[now].r)>>1;    if(l<=m)    query_max(l,r,lson);    if(r>m) query_max(l,r,rson);}inline void dfs1(int now,int fa){    father[now]=fa;    size[now]=1;    depth[now]=depth[fa]+1;    for(int u=first[now];u;u=edge[u].next)    {        int vis=edge[u].to;        if(vis==fa) continue;        dfs1(vis,now);        size[now]+=size[vis];        if(size[vis]>size[maxson[now]]) maxson[now]=vis;    }}inline void dfs2(int now,int topf){    id[now]=++sign;    top[now]=topf;    wnew[sign]=val[now];    if(maxson[now]) dfs2(maxson[now],topf);    for(int u=first[now];u;u=edge[u].next)    {        int vis=edge[u].to;        if(vis==father[now]||vis==maxson[now])  continue;        dfs2(vis,vis);    }}inline int qmax(int x,int y){    int ret=-INF;    while(top[x]!=top[y])    {        if(depth[top[x]]
     
      >n;    for(int i=1;i<=n-1;i++)    {        int x,y;        cin>>x>>y;        addedge(x,y);        addedge(y,x);    }    for(int i=1;i<=n;i++)   cin>>val[i];    dfs1(1,0);    dfs2(1,1);    build(1,n,1);    int Q;    cin>>Q;    while(Q--)    {        string s;        int x,y;        cin>>s>>x>>y;        if(s=="CHANGE") update(1,id[x],y);        if(s=="QMAX") cout<
      
       <<'\n';        if(s=="QSUM") cout<
       
        <<'\n';    }    return  0;}