「模板」树链剖分

简要说明

本题基于例题 luoguOJ-P3384 。

对于树链剖分（我更喜欢叫重链剖分），因为它需要定义的东西比较多，对于参数，这里给出一张表格说明

dep[u]	点 \(u\) 的深度
fa[u]	点 \(u\) 在树上的深度
dfn[u]	点 \(u\) 的 \(dfs\) 序
siz[u]	\(u\) 的子树大小
top[u]	\(u\) 属于的重链的深度最浅的点编号（不是其 \(dfs\) 序）
son[u]	\(u\) 的重儿子
ncnt	编写 \(dfs\) 序的时间戳
w[u]	点 \(u\) 的初始值
wt[id]	\(dfs\) 序为 \(id\) 的点的初始值
tre[i]	线段树，编号为 \(i\) 的节点及以下的值的和，具体是什么见代码
laz[i]	相应的懒标记
dfs1()	第一个 \(dfs\) ，处理掉 dep,fa,son,siz 数组
dfs2()	第二个 \(dfs\) ，处理掉 dfn,wt,top 数组

模板

下面给出代码

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

#define rep(i,__l,__r) for(signed i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(signed i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
#define LL long long
#define ull unsigned long long
#define uint unsigned int
#define pii pair<int,int>
#define Endl putchar('\n')
// #define FILEOI
// #define int long long
// #define int unsigned

#ifdef FILEOI
# define MAXBUFFERSIZE 500000
    inline char fgetc(){
        static char buf[MAXBUFFERSIZE+5],*p1=buf,*p2=buf;
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXBUFFERSIZE,stdin),p1==p2)?EOF:*p1++;
    }
# undef MAXBUFFERSIZE
# define cg (c=fgetc())
#else
# define cg (c=getchar())
#endif
template<class T>inline void qread(T& x){
    char c;bool f=0;
    while(cg<'0'||'9'<c)f|=(c=='-');
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    if(f)x=-x;
}
inline int qread(){
    int x=0;char c;bool f=0;
    while(cg<'0'||'9'<c)f|=(c=='-');
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    return f?-x:x;
}
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline int gcd(const int a,const int b){return b?gcd(b,a%b):a;}
inline void getInv(int inv[],const int lim,const int MOD){
    inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
    if(x<0)return (void)(putchar('-'),fwrit(-x));
    if(x>9)fwrit(x/10);putchar(x%10^48);
}
inline LL mulMod(const LL a,const LL b,const LL mod){//long long multiplie_mod
    return ((a*b-(LL)((long double)a/mod*b+1e-8)*mod)%mod+mod)%mod;
}

const int MAXN=1e5;

int n,m,r,mod;

struct edge{
    int to,nxt;
    edge(const int T=0,const int N=0):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt;
inline void add_edge(const int u,const int v){
    e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
}

int dep[MAXN+5],fa[MAXN+5],dfn[MAXN+5],siz[MAXN+5],top[MAXN+5],son[MAXN+5],ncnt;
int w[MAXN+5],wt[MAXN+5];

int tre[MAXN<<2|3],laz[MAXN<<2|3];//segment tree
#define lc (i<<1)
#define rc (i<<1|1)
#define mid (l+r>>1)
#define inlen (r-l+1)
#define linter lc,l,mid
#define rinter rc,mid+1,r
inline void pushdown(const int i,const int len){
    laz[lc]+=laz[i];
    laz[rc]+=laz[i];
    tre[lc]=(0ll+tre[lc]+1ll*laz[i]*(len-(len>>1)))%mod;
    tre[rc]=(0ll+tre[rc]+1ll*laz[i]*(len>>1))%mod;
    laz[i]=0;
}
inline void pushup(const int i){
    tre[i]=(tre[lc]+tre[rc])%mod;
}
inline void modify(const int i,const int l,const int r,const int L,const int R,const int k){
    if(L<=l && r<=R){
        laz[i]+=k;
        tre[i]+=k*inlen;
    }
    else{
        if(laz[i])pushdown(i,inlen);
        if(L<=mid)modify(linter,L,R,k);
        if(mid<R)modify(rinter,L,R,k);
        pushup(i);
    }
}
inline int query(const int i,const int l,const int r,const int L,const int R){
    if(L<=l && r<=R)return tre[i];
    else{
        int ret=0;
        if(laz[i])pushdown(i,inlen);
        if(L<=mid)ret=query(linter,L,R)%mod;
        if(mid<R)ret=(0ll+ret+query(rinter,L,R))%mod;
        return ret;
    }
}
inline void buildtre(const int i,const int l,const int r){
    if(l==r){
        tre[i]=wt[l];
        return;
    }
    buildtre(linter);
    buildtre(rinter);
    pushup(i);
}

inline void dfs1(const int u,const int f,const int depth){
    dep[u]=depth;
    fa[u]=f;
    siz[u]=1;
    int maxsize=-1;
    for(int i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=f){
        dfs1(v,u,depth+1);
        siz[u]+=siz[v];
        if(siz[v]>maxsize)son[u]=v,maxsize=siz[v];
    }
}

inline void dfs2(const int u,const int bel){
    dfn[u]=++ncnt;
    wt[ncnt]=w[u];
    top[u]=bel;
    if(!son[u])return;
    dfs2(son[u],bel);
    for(int i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=fa[u] && v!=son[u])
        dfs2(v,v);
}

inline void modiRange(int u,int v,const int k){
    while(top[u]^top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify(1,1,n,dfn[top[u]],dfn[u],k);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    modify(1,1,n,dfn[u],dfn[v],k);
}

inline int queRange(int u,int v){
    int ret=0;
    while(top[u]^top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        (ret+=query(1,1,n,dfn[top[u]],dfn[u]))%=mod;
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    (ret+=query(1,1,n,dfn[u],dfn[v]))%=mod;
    return ret;
}

signed main(){
#ifdef FILEOI
    freopen("file.in","r",stdin);
    freopen("file.out","w",stdout);
#endif
    qread(n,m,r,mod);
    rep(i,1,n)w[i]=qread()%mod;
    for(int i=1,u,v;i<n;++i){
        qread(u,v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    buildtre(1,1,n);
    int opt,x,y,z;
    while(m--){
        qread(opt,x);
        if(opt==1){
            qread(y,z);z%=mod;
            modiRange(x,y,z);
        }
        else if(opt==2){
            qread(y);
            writc(queRange(x,y),'\n');
        }
        else if(opt==3){
            z=qread()%mod;
            modify(1,1,n,dfn[x],dfn[x]+siz[x]-1,z);
        }
        else writc(query(1,1,n,dfn[x],dfn[x]+siz[x]-1),'\n');
    }
    return 0;
}