【数据结构】——树链剖分

树链剖分——简单而强大的数据维护方法

只是放个板子而已。

用我的码风覆盖了的。

#include<bits/stdc++.h>
using namespace std;
//------------------------------------------------------
inline int read(){
    int f=1,x=0;
    char c=getchar();
    while(!isdigit(c)){
        if(c==‘-‘) f=-1;
        c=getchar();
    } 
    while(isdigit(c)){
        x=x*10+c-‘0‘;
        c=getchar();
    } 
    return x*f;
}
//------------------------------------------------------
const int N=2e5+10;
int at[N<<1],sum[N<<1];
int head[N],cnt,n,m,r,mod,tot,ans;
int w[N],dep[N],siz[N],fa[N],son[N],top[N],id[N],w2[N];
struct edge{ int to,next; }e[N<<1];
inline void addedge(int from,int to){ e[++cnt]=(edge){to,head[from]};head[from]=cnt; }
inline void add(int x,int y){addedge(x,y),addedge(y,x);}
//-------------------------------------------------------
void dfs1(int u,int f){
    dep[u]=dep[f]+1;
    siz[u]=1;
    fa[u]=f;
    int maxson=0;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>maxson) maxson=siz[v],son[u]=v;
    }
}
void dfs2(int u,int f){
    id[u]=++tot;
    w2[tot]=w[u];
    top[u]=f;
    if(!son[u]) return;
    dfs2(son[u],f);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
//-------------------------------------------------------
class Tree{
    private:
        inline int ls(int o){return o<<1;}
        inline int rs(int o){return o<<1|1;}
        inline void pushdown(int o,int l,int r){
            if(!at[o]) return;
            int mid=(l+r)>>1;
            sum[ls(o)]=(sum[ls(o)]+at[o]*(mid-l+1))%mod;
            sum[rs(o)]=(sum[rs(o)]+at[o]*(r-mid))%mod;
            at[ls(o)]=(at[ls(o)]+at[o])%mod;
            at[rs(o)]=(at[rs(o)]+at[o])%mod;
            at[o]=0;
        }
        inline void pushup(int o){ sum[o]=(sum[ls(o)]+sum[rs(o)])%mod;}
    public:
        void build(int o,int l,int r){
            if(l==r){
                sum[o]=w2[l];
                if(sum[o]>mod) sum[o]%=mod;
                return;
            }
            int mid=(l+r)>>1;
            build(ls(o),l,mid);
            build(rs(o),mid+1,r);
            pushup(o);
        }
        void change(int o,int l,int r,int x,int y,int k){
            if(l>y||r<x) return;
            if(x<=l&&r<=y){
                sum[o]+=(r-l+1)*k;
                at[o]+=k;
                return;
            }
            int mid=(l+r)>>1;
            pushdown(o,l,r);
            if(x<=mid) change(ls(o),l,mid,x,y,k);
            if(y>mid) change(rs(o),mid+1,r,x,y,k);
            pushup(o);
        }
        void query(int o,int l,int r,int x,int y){
            if(l>y||r<x) return;
            if(x<=l&&r<=y){
                ans+=sum[o];
                ans%=mod;
                return;
            }
            int mid=(l+r)>>1;
            pushdown(o,l,r);
            if(x<=mid) query(ls(o),l,mid,x,y);
            if(y>mid) query(rs(o),mid+1,r,x,y);
        }
        inline int ask(int u,int v){
            int cur=0;
            while(top[u]!=top[v]){
                if(dep[top[u]]<dep[top[v]]) swap(u,v);
                ans=0;
                query(1,1,n,id[top[u]],id[u]);
                cur+=ans;
                cur%=mod;
                u=fa[top[u]];
            }
            ans=0;
            if(dep[u]>dep[v]) swap(u,v);
            query(1,1,n,id[u],id[v]);
            cur+=ans;
            return cur%mod;
        }
        inline void ask2(int u,int v,int k){
            k%=mod;
            while(top[u]!=top[v]){
                if(dep[top[u]]<dep[top[v]]) swap(u,v);
                change(1,1,n,id[top[u]],id[u],k);
                u=fa[top[u]];
            }
            if(dep[u]>dep[v]) swap(u,v);
            change(1,1,n,id[u],id[v],k);
        }    
}T;
//-------------------------------------------------------
int main(){
    n=read();m=read();r=read();mod=read();
    int k,x,y,z;
    for(register int i=1;i<=n;i++) w[i]=read();
    for(register int i=1;i<n;i++) add(read(),read());
    dfs1(r,0);
    dfs2(r,r);
    T.build(1,1,n);
    for(register int i=1;i<=m;i++){
        k=read();
        if(k==1){
            x=read();y=read();z=read();
            T.ask2(x,y,z);
        }
        else if(k==2){
            x=read();y=read();
            printf("%d\n",T.ask(x,y));
        }
        else if(k==3){
            x=read();z=read();
            T.change(1,1,n,id[x],id[x]+siz[x]-1,z);
        }
        else{
            x=read();ans=0;
            T.query(1,1,n,id[x],id[x]+siz[x]-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}