【ZJOI2008】【树链剖分】树的统计

题目链接:https://www.luogu.org/problemnew/show/P2590

这题可能存在的难点在于线段树的维护

单点修改连标记都不用打,直接$pushup$就行(怎么就成紫题了呢?

解决了维护的问题剩下的就是树链剖分模板了

上代码↓

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=1<<15,INF=2e9;

int n,m,x,y,np,cnt;
int sn[MAXN],siz[MAXN],tp[MAXN],top[MAXN];
int h[MAXN],val[MAXN],ren[MAXN],id[MAXN],fa[MAXN];
int tree[MAXN<<1],maxn[MAXN<<1];
char ch[101];
struct rpg{
    int li,nx;
}a[MAXN<<1];

inline int read(){
    int x=0,fl=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') fl=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*fl;
}

void add(int ls,int nx){
    a[++np]=(rpg){h[ls],nx};
    h[ls]=np;
}

void init(){
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        x=read(),y=read();
        add(x,y);add(y,x);
    }for(int i=1;i<=n;++i){
        val[i]=read();
    }return;
}

void dfs1(int x,int f,int deep){
    tp[x]=deep;
    fa[x]=f;
    siz[x]=1;
    int hwy=0;
    for(int i=h[x];i;i=a[i].li){
        if(a[i].nx!=f){
            dfs1(a[i].nx,x,deep+1);
            siz[x]+=siz[a[i].nx];
            if(siz[a[i].nx]>hwy){
                sn[x]=a[i].nx;
                hwy=siz[a[i].nx];
            }
        }
    }return;
}

void dfs2(int x,int tpx){
    id[x]=++cnt;
    ren[cnt]=val[x];
    top[x]=tpx;
    if(!sn[x]) return;
    dfs2(sn[x],tpx);
    for(int i=h[x];i;i=a[i].li){
        if(a[i].nx!=fa[x]&&a[i].nx!=sn[x]){
            dfs2(a[i].nx,a[i].nx);
        }
    }return;
}

void build(int k,int l,int r){
    if(l==r){
        tree[k]=maxn[k]=ren[l];
        return;
    }int i=k<<1,mid=l+r>>1;
    build(i,l,mid);
    build(i|1,mid+1,r);
    tree[k]=tree[i]+tree[i|1];
    maxn[k]=max(maxn[i],maxn[i|1]);
}

int askmax(int k,int l,int r,int le,int ri){
    if(le<=l&&r<=ri) return maxn[k];
    int i=k<<1,mid=l+r>>1;
    int ans=-INF;
    if(le<=mid) ans=max(ans,askmax(i,l,mid,le,ri));
    if(mid<ri) ans=max(ans,askmax(i|1,mid+1,r,le,ri));
    return ans;
}

int asksum(int k,int l,int r,int le,int ri){
    if(le<=l&&r<=ri) return tree[k];
    int i=k<<1,mid=l+r>>1;
    int ans=0;
    if(le<=mid) ans+=asksum(i,l,mid,le,ri);
    if(mid<ri) ans+=asksum(i|1,mid+1,r,le,ri);
    return ans;
}

int askmx(int x,int y){
    int ans=-INF;
    while(top[x]!=top[y]){
        if(tp[top[x]]<tp[top[y]]) swap(x,y);
        ans=max(ans,askmax(1,1,n,id[top[x]],id[x]));
        x=fa[top[x]];
    }if(tp[x]>tp[y]) swap(x,y);
    ans=max(ans,askmax(1,1,n,id[x],id[y]));
    return ans;
}

int asksm(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(tp[top[x]]<tp[top[y]]) swap(x,y);
        ans+=asksum(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }if(tp[x]>tp[y]) swap(x,y);
    ans+=asksum(1,1,n,id[x],id[y]);
    return ans;
}

void cchg(int k,int l,int r,int p,int x){
    if(l==r){
        tree[k]=maxn[k]=x;
        return;
    }int i=k<<1,mid=l+r>>1;
    if(p<=mid) cchg(i,l,mid,p,x);
    else cchg(i|1,mid+1,r,p,x);
    tree[k]=tree[i]+tree[i|1];
    maxn[k]=max(maxn[i],maxn[i|1]);
}

void solve(){
    scanf("%d",&m);
    while(m--){
        scanf("%s",ch);x=read(),y=read();
        if(ch[1]=='M') printf("%d\n",askmx(x,y));
        else if(ch[1]=='S') printf("%d\n",asksm(x,y));
        else cchg(1,1,n,id[x],y);
    }return;
}

int main(){
    init();
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n);
    solve();
    return 0;
}