1. 题目

传送门=￣ω￣=

2. 题解

树链剖分模板题。
先剖树成链，再用线段树维护一条一条的链。
线段树连懒惰标记都不用，单点修改

代码：

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
#define NS (30005)
using namespace std;
struct N{int l,r,max,sum;N(){l=r=max=sum=0;}}e[NS<<2];
int n,fa[NS],dep[NS],siz[NS],pos[NS],top[NS],w[NS],cnt=1,q;
char opt[10];
vector<int> g[NS];
void update(int a)
{e[a].max=max(e[LS(a)].max,e[RS(a)].max),e[a].sum=e[LS(a)].sum+e[RS(a)].sum;}
void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r;
    if(l==r){e[a].sum=e[a].max=w[l];return;}
    build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a)),update(a);
}
void change(int x,int k,int a)
{
    if(e[a].l==x&&e[a].r==x){e[a].sum=e[a].max=k;return;}
    if(x<=((e[a].l+e[a].r)>>1))change(x,k,LS(a));
    else change(x,k,RS(a));
    update(a);
}
int query_sum(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].sum;
    int tot=0;
    if(l<=((e[a].l+e[a].r)>>1))tot+=query_sum(l,r,LS(a));
    if(r>((e[a].l+e[a].r)>>1))tot+=query_sum(l,r,RS(a));
    return tot;
}
int query_max(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].max;
    int tot=INT_MIN;
    if(l<=((e[a].l+e[a].r)>>1))tot=max(tot,query_max(l,r,LS(a)));
    if(r>((e[a].l+e[a].r)>>1))tot=max(tot,query_max(l,r,RS(a)));
    return tot;
}
void init1(int u)
{
    siz[u]=1,dep[u]=dep[fa[u]]+1;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u])fa[g[u][i]]=u,init1(g[u][i]),siz[u]+=siz[g[u][i]];
}
void init2(int u)
{
    int nxt=0,maxn=0;pos[u]=cnt++;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&siz[g[u][i]]>maxn)nxt=g[u][i],maxn=siz[g[u][i]];
    if(!nxt)return;
    top[nxt]=top[u],init2(nxt);
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&g[u][i]!=nxt)
            top[g[u][i]]=g[u][i],init2(g[u][i]);
}
int query(int a,int b,bool f)
{
    int tot=f?0:INT_MIN;
    while(top[a]!=top[b])
    {
        if(dep[top[a]]>dep[top[b]])swap(a,b);
        if(f)tot+=query_sum(pos[top[b]],pos[b],1);
        else tot=max(tot,query_max(pos[top[b]],pos[b],1));
        b=fa[top[b]];
    }
    if(pos[a]>pos[b])swap(a,b);
    if(f)tot+=query_sum(pos[a],pos[b],1);
    else tot=max(tot,query_max(pos[a],pos[b],1));
    return tot;
}
int main()
{
    scanf("%d",&n);
    for(int i=1,a,b;i<n;i++)
        scanf("%d%d",&a,&b),g[a].push_back(b),g[b].push_back(a);
    init1(1),top[1]=1,init2(1);
    for(int i=1;i<=n;i++)scanf("%d",&w[pos[i]]);
    build(0,cnt-1,1),scanf("%d",&q);
    for(int i=1,a,b;i<=q;i++)
    {
        scanf("%s%d%d",opt,&a,&b);
        if(!strcmp(opt,"CHANGE"))change(pos[a],b,1);
        else if(!strcmp(opt,"QMAX"))printf("%d\n",query(a,b,0));
        else printf("%d\n",query(a,b,1));
    }
    return 0;
}