【樹鍊剖分+線段樹】BZOJ1036 [ZJOI2008]樹的統計Count

題面在這裡

典型的樹鍊剖分……不解釋了

不懂的可以看這裡

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=,maxe=;
int n,q;
int son[maxe],nxt[maxe],lnk[maxn],tot;
void add(int x,int y){
    son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline int red(){
    int tot=,f=;char ch=getchar();
    while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=getchar();}
    while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
    return tot*f;
}
int siz[maxn],fa[maxn],dep[maxn],H_son[maxn],top[maxn],id[maxn],tim;
void dfs1(int x){
    siz[x]=;dep[x]=dep[fa[x]]+;
    for (int j=lnk[x];j;j=nxt[j])
     if (fa[x]!=son[j]){
        fa[son[j]]=x;dfs1(son[j]);
        if (siz[son[j]]>siz[H_son[x]]) H_son[x]=son[j];
        siz[x]+=siz[son[j]];
     }
}
void dfs2(int x,int lst){
    top[x]=lst;id[x]=++tim;
    if (H_son[x]) dfs2(H_son[x],lst);
    for (int j=lnk[x];j;j=nxt[j])
     if (fa[x]!=son[j]&&H_son[x]!=son[j]) dfs2(son[j],son[j]);
}
struct node{
    int x,l,r,mx,s;
    node(int x=,int y=) {l=x,r=y;x=mx=s=;}
}tre[maxn*];
void buildtree(int x,int l,int r){
    tre[x]=node(l,r);
    if (l==r) return;
    int mid=l+r>>;
    buildtree(x<<,l,mid);buildtree(x<<|,mid+,r);
}
void ist(int x,int k,int w){
    if (k<tre[x].l||tre[x].r<k) return;
    if (tre[x].l==tre[x].r) {tre[x].x=tre[x].mx=tre[x].s=w;return;}
    ist(x<<,k,w);ist(x<<|,k,w);
    tre[x].mx=max(tre[x<<].mx,tre[x<<|].mx);
    tre[x].s=tre[x<<].s+tre[x<<|].s;
}
int qrymx(int x,int l,int r){
    if (r<tre[x].l||tre[x].r<l) return ;
    if (l<=tre[x].l&&tre[x].r<=r) return tre[x].mx;
    return max(qrymx(x<<,l,r),qrymx(x<<|,l,r));
}
int qrys(int x,int l,int r){
    if (r<tre[x].l||tre[x].r<l) return ;
    if (l<=tre[x].l&&tre[x].r<=r) return tre[x].s;
    return qrys(x<<,l,r)+qrys(x<<|,l,r);
}
int askmx(int x,int y){
    int res=;
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        res=max(res,qrymx(,id[top[x]],id[x]));
        x=fa[top[x]];
    }
    if (id[x]>id[y]) swap(x,y);
    res=max(res,qrymx(,id[x],id[y]));
    return res;
}
int asks(int x,int y){
    int res=;
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        res+=qrys(,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if (id[x]>id[y]) swap(x,y);
    res+=qrys(,id[x],id[y]);
    return res;
}
int main(){
    n=red();
    for (int i=,x,y;i<n;i++) x=red(),y=red(),add(x,y),add(y,x);
    dep[]=siz[]=fa[]=tim=;
    dfs1();dfs2(,);
    buildtree(,,n);
    for (int i=;i<=n;i++) ist(,id[i],red());
    q=red();
    while (q--){
        char s[];scanf("%s",s);
        if (s[]=='H'){
            int u=red(),t=red();
            ist(,id[u],t);
        }else
        if (s[]=='M'){
            int x=red(),y=red();
            printf("%d\n",askmx(x,y));
        }else{
            int x=red(),y=red();
            printf("%d\n",asks(x,y));
        }
    }
    return ;
}