Luogu - P3384 树链剖分模板

Luogu - P3384

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define println(a) printf("%lld\n",(ll)a)
using namespace std;
const int MAXN = 2e5+11;
typedef long long ll;
ll MOD;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int to[MAXN<<1],nxt[MAXN<<1],head[MAXN],tot; ll cost[MAXN<<1];
void add(int u,int v,ll w=0){
    to[tot]=v;
    cost[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot++;
}
int size[MAXN],dfn[MAXN],dfned[MAXN],pre[MAXN],p[MAXN],son[MAXN],dep[MAXN],top[MAXN],CLOCK;
void init(){
    memset(head,-1,sizeof head);
    memset(son,0,sizeof son);
    tot=CLOCK=0;
}
void dfs(int u,int fa,int d){
    p[u]=fa; dep[u]=d; size[u]=1;
    son[u]=top[u]=0;
    for(int i=head[u];~i;i=nxt[i]){
        int v=to[i];
        if(v==fa) continue;
        dfs(v,u,d+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]]){
            son[u]=v;
        }
    }
}
void dfs2(int u,int tp){
    top[u]=tp;
    dfn[u]=++CLOCK;
    pre[CLOCK]=u;
    if(son[u]) dfs2(son[u],tp);
    for(int i=head[u];~i;i=nxt[i]){
        int v=to[i];
        if(v==p[u]||v==son[u]) continue;
        dfs2(v,v);
    }
    dfned[u]=CLOCK; 
}
int a[MAXN];
struct ST{
    ll sum[MAXN<<2];
    int lazy[MAXN<<2];
    #define lc o<<1
    #define rc o<<1|1
    void pu(int o){
        sum[o]=sum[lc]+sum[rc];
        if(sum[o]>=MOD) sum[o]%=MOD;
    }
    void build(int o,int l,int r){
        sum[o]=lazy[o]=0;
        if(l==r){
            sum[o]=a[pre[l]]; //!!
            return;
        }
        int mid=l+r>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        pu(o);
    }
    void pd(int o,int l,int r){
        if(lazy[o]){
            int mid=l+r>>1;
            sum[lc]+=(ll)(mid-l+1)*lazy[o];
            sum[rc]+=(ll)(r-mid)*lazy[o];
            if(sum[lc]>MOD) sum[lc]%=MOD;
            if(sum[rc]>MOD) sum[rc]%=MOD;
            lazy[lc]+=lazy[o];
            lazy[rc]+=lazy[o];
            lazy[o]=0;
        }
    }
    void update(int o,int l,int r,int L,int R,ll v){
        if(L<=l&&r<=R){
            sum[o]+=(ll)(r-l+1)*v;
            if(sum[o]>=MOD) sum[o]%=MOD;
            lazy[o]+=v;
            return;
        }
        pd(o,l,r);
        int mid=l+r>>1;
        if(L<=mid) update(lc,l,mid,L,R,v);
        if(R>mid) update(rc,mid+1,r,L,R,v);
        pu(o);
    }
    ll query(int o,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            return sum[o];
        }
        pd(o,l,r);
        int mid=l+r>>1;
        ll ans=0;
        if(L<=mid) ans+=query(lc,l,mid,L,R);
        if(R>mid) ans+=query(rc,mid+1,r,L,R);
        return ans>=MOD?ans%MOD:ans;
    }
}st;
void solve(int u,int v,int val,int op){
    ll ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        if(op==2) ans+=st.query(1,1,CLOCK,dfn[top[u]],dfn[u]);
        if(op==2&&ans>=MOD) ans%=MOD;
        else st.update(1,1,CLOCK,dfn[top[u]],dfn[u],val);
        u=p[top[u]];
    }
    //same link
    if(dep[u]<dep[v]) swap(u,v);
    if(op==2) ans+=st.query(1,1,CLOCK,dfn[v],dfn[u]);//att
    if(op==2&&ans>=MOD) ans%=MOD;
    else st.update(1,1,CLOCK,dfn[v],dfn[u],val);
    if(op==2) println(ans%MOD);
}
int main(){
    int n,m,rt;
    while(cin>>n>>m>>rt>>MOD){
        init();
        rep(i,1,n) a[i]=read();
        rep(i,1,n-1){
            int u=read();
            int v=read();
            add(u,v);
            add(v,u);
        }
        dfs(rt,-1,1); dfs2(rt,rt);
        st.build(1,1,CLOCK);
        while(m--){
            int op=read();
            if(op==1){
                int u=read();
                int v=read();
                ll val=read();
                solve(u,v,val,op);
            }else if(op==2){
                int u=read();
                int v=read();
                solve(u,v,0,op);
            }else if(op==3){
                int x=read();
                ll v=read();
                int l=dfn[x],r=dfned[x];
                st.update(1,1,CLOCK,l,r,v);
            }else{
                int x=read();
                int l=dfn[x],r=dfned[x];
                println(st.query(1,1,CLOCK,l,r)%MOD);
            }
        }
    }
    return 0;
}