题意

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。

我们将以下面的形式来要求你对这棵树完成一些操作：

I. CHANGE u t : 把结点u的权值改为t

II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

注意：从点u到点v的路径上的节点包括u和v本身

对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

分析

树剖模板题。时间复杂度\(O(n + q\log n)\)

代码

BZOJ因为我那个major不让我过编译……只好在洛谷上交了。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;
    rg char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x){
    return x=read<T>();
}
typedef long long ll;

co int N=3e4+1;
std::vector<int> g[N];
int n,w[N],fa[N],dep[N],siz[N],son[N],top[N],pos[N],dfn,ref[N];
namespace T{
    int max[N*4],sum[N*4];
#define lson x<<1
#define rson x<<1|1
    void pushup(int x){
        max[x]=std::max(max[lson],max[rson]);
        sum[x]=sum[lson]+sum[rson];
    }
    void build(int x,int l,int r){
        if(l==r){
            max[x]=sum[x]=w[ref[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(lson,l,mid),build(rson,mid+1,r);
        pushup(x);
    }
    void modify(int x,int l,int r,int p,int v){
        if(l==r){
            max[x]=sum[x]=v;
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid) modify(lson,l,mid,p,v);
        else modify(rson,mid+1,r,p,v);
        pushup(x);
    }
    int major(int x,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return max[x];
        int mid=(l+r)>>1;
        if(qr<=mid) return major(lson,l,mid,ql,qr);
        if(ql>mid) return major(rson,mid+1,r,ql,qr);
        return std::max(major(lson,l,mid,ql,qr),major(rson,mid+1,r,ql,qr));
    }
    int summation(int x,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return sum[x];
        int mid=(l+r)>>1;
        if(qr<=mid) return summation(lson,l,mid,ql,qr);
        if(ql>mid) return summation(rson,mid+1,r,ql,qr);
        return summation(lson,l,mid,ql,qr)+summation(rson,mid+1,r,ql,qr);
    }
}
void dfs1(int x,int fa){
    ::fa[x]=fa,dep[x]=dep[fa]+1,siz[x]=1;
    for(int i=0;i<g[x].size();++i){
        int y=g[x][i];
        if(y==fa) continue;
        dfs1(y,x),siz[x]+=siz[y];
        if(siz[y]>siz[son[x]]) son[x]=y;
    }
}
void dfs2(int x,int top){
    ::top[x]=top,pos[x]=++dfn,ref[dfn]=x;
    if(!son[x]) return;
    dfs2(son[x],top);
    for(int i=0;i<g[x].size();++i){
        int y=g[x][i];
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}
void modify(int x,int v){
    T::modify(1,1,n,pos[x],v);
}
int major(int x,int y){
    int ans=-30000;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
        ans=std::max(ans,T::major(1,1,n,pos[top[x]],pos[x]));
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) std::swap(x,y);
    ans=std::max(ans,T::major(1,1,n,pos[y],pos[x]));
    return ans;
}
int summation(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
        ans+=T::summation(1,1,n,pos[top[x]],pos[x]);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) std::swap(x,y);
    ans+=T::summation(1,1,n,pos[y],pos[x]);
    return ans;
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);
    for(int i=1;i<n;++i){
        int x=read<int>(),y=read<int>();
        g[x].push_back(y),g[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
        read(w[i]);
    dfs1(1,0),dfs2(1,1);
    T::build(1,1,n);
    int q=read<int>();
    char cmd[10];
    while(q--){
        scanf("%s",cmd);
        if(cmd[1]=='H'){
            int x=read<int>(),v=read<int>();
            modify(x,v);
        }
        else if(cmd[1]=='M'){
            int x=read<int>(),y=read<int>();
            printf("%d\n",major(x,y));
        }
        else{
            int x=read<int>(),y=read<int>();
            printf("%d\n",summation(x,y));
        }
    }
    return 0;
}