Luogu

分析

树剖板子。

线段树支持单点赋值、区间求和、区间最大值即可。

这个线段树还比较好写

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=30010;
const int INF=2147483647;

struct Edge { int v,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n;
int a[MAXN];
int real[MAXN],dep[MAXN],fa[MAXN],sz[MAXN],hson[MAXN],top[MAXN],id[MAXN];
int tot=0;

inline void Dfs1(int u,int f) {
    fa[u]=f,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==f) continue;
        dep[v]=dep[u]+1;
        Dfs1(v,u);
        sz[u]+=sz[v];
        if (!hson[u]||sz[v]>sz[hson[u]]) hson[u]=v;
    }
}

inline void Dfs2(int u,int anc) {
    top[u]=anc,id[u]=++tot,real[tot]=u;
    if (!hson[u]) return;
    Dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v!=fa[u]&&v!=hson[u]) Dfs2(v,v);
    }
}

struct Segment_Tree {
    int sumv[MAXN<<2],maxv[MAXN<<2];
#define lson (o<<1)
#define rson (o<<1|1)
    inline void pushup(int o) {
        sumv[o]=sumv[lson]+sumv[rson];
        maxv[o]=max(maxv[lson],maxv[rson]);
    }
    inline void build(int o,int l,int r) {
        if (l==r) { sumv[o]=maxv[o]=a[real[l]]; return; }
        int mid=(l+r)>>1;
        build(lson,l,mid);
        build(rson,mid+1,r);
        pushup(o);
    }
    inline void update(int o,int l,int r,int p,int v) {
        if (l==r) { sumv[o]=maxv[o]=v; return; }
        int mid=(l+r)>>1;
        if (p<=mid) update(lson,l,mid,p,v);
        if (p>mid) update(rson,mid+1,r,p,v);
        pushup(o);
    }
    inline int querysum(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return sumv[o];
        int mid=(l+r)>>1,rt=0;
        if (ql<=mid) rt+=querysum(lson,l,mid,ql,qr);
        if (qr>mid) rt+=querysum(rson,mid+1,r,ql,qr);
        pushup(o);
        return rt;
    }
    inline int querymax(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return maxv[o];
        int mid=(l+r)>>1,rt=-INF;
        if (ql<=mid) rt=querymax(lson,l,mid,ql,qr);
        if (qr>mid) rt=max(rt,querymax(rson,mid+1,r,ql,qr));
        pushup(o);
        return rt;
    }
#undef lson
#undef rson
};

Segment_Tree T;

inline void change(int u,int v) { T.update(1,1,n,id[u],v); }
inline int qsum(int u,int v) {
    int tu=top[u],tv=top[v],ans=0;
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) { swap(tu,tv); swap(u,v); }
        ans+=T.querysum(1,1,n,id[tu],id[u]);
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    ans+=T.querysum(1,1,n,id[v],id[u]);
    return ans;
}
inline int qmax(int u,int v) {
    int tu=top[u],tv=top[v],ans=-INF;
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) { swap(tu,tv); swap(u,v); }
        ans=max(ans,T.querymax(1,1,n,id[tu],id[u]));
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    ans=max(ans,T.querymax(1,1,n,id[v],id[u]));
    return ans;
}

char tmp[20];

int main() {
    n=read();
    for (re int i=1,u,v;i<n;i++) {
        u=read(),v=read();
        addEdge(u,v); addEdge(v,u);
    }
    for (re int i=1;i<=n;i++) a[i]=read();
    dep[1]=1; Dfs1(1,0); Dfs2(1,1); T.build(1,1,n);
    int T=read();
    while (T--) {
        scanf("%s",tmp+1); char c=tmp[2];
        int x=read(),y=read();
        if (c=='H') change(x,y);
        else if (c=='S') printf("%d\n",qsum(x,y));
        else if (c=='M') printf("%d\n",qmax(x,y));
    }
    return 0;
}