树链剖分模板

#include<cstdio>
#include<iostream>
#include<vector>
#define tx top[x]
#define ty top[y]
#define ls o<<1
#define rs o<<1|1
#define M ((L+R)>>1)
using namespace std;
const int maxn = 100010;

int n, m, P ,root, tot;
int A[maxn], fa[maxn], deep[maxn], num[maxn], son[maxn], ID[maxn], top[maxn], fID[maxn];
int sumv[maxn*4],addv[maxn*4];
vector<int> G[maxn];

void addedge(int x,int y) {
    G[x].push_back(y);
}

int dfs1(int x,int dep) { //返回包括自己，子树的大小 
    deep[x] = dep;
    int ret = 1;
    int len = G[x].size();
    int MX = 0;
    for(int i = 0;i < len;i++) {
        int tp = G[x][i];
        if(fa[x] == tp) continue;
        fa[tp] = x;
        int back = dfs1(tp,dep+1);
        if(back > MX) {
            son[x] = tp;
            MX = back;    
        } 
        ret += back;
    }
    num[x] = ret;
    return ret;
}

void dfs2(int x) {
    if(x == 0) return;
    ID[x] = ++tot;
    fID[tot] = x;
    if(son[fa[x]] == x) top[x] = top[fa[x]];
    else top[x] = x; 
    int len = G[x].size();
    dfs2(son[x]);
    for(int i = 0;i < len;i++) {
        int tp = G[x][i];
        if(tp != fa[x] && tp != son[x]) dfs2(tp);
    }
}

inline void build(int o,int L,int R) {
    if(L == R) {
        sumv[o] = A[fID[L]]%P;
        return;
    }
    build(ls,L,M);
    build(rs,M+1,R);
    sumv[o] = (sumv[ls] + sumv[rs])%P;
}

inline void pushdown(int o,int L,int R) {
    (addv[ls] += addv[o])%=P;
    (addv[rs] += addv[o])%=P;
    (sumv[ls] += addv[o]*(M-L+1))%=P;
    (sumv[rs] += addv[o]*(R-M))%=P;
    addv[o] = 0;
}

int ql,qr,qa;
inline void update(int o,int L,int R) {
    if(ql <= L && R <= qr) {
        (addv[o] += qa)%=P;
        (sumv[o] += qa*(R-L+1))%=P;
        return;
    }
    pushdown(o,L,R);
    if(ql <= M) update(ls,L,M);
    if(qr > M) update(rs,M+1,R);
    sumv[o] = (sumv[ls] + sumv[rs])%P;
}

inline int query(int o,int L,int R) {
    if(ql <= L && R <= qr) return sumv[o]%P;
    int ret = 0;
    pushdown(o,L,R);
    if(ql <= M) (ret += query(ls,L,M))%=P;
    if(qr > M) (ret += query(rs,M+1,R))%=P;
    return ret%P; 
}


int LCA(int x,int y) {
    int ret = 0;
    while(tx != ty) {
        if(deep[tx] >= deep[ty]) {
            //x 走到 top[x]（编号小） 的 爸爸 ,top[x] 的爸爸是轻链 
            ql = ID[tx], qr = ID[x];//下闭上开 
            (ret += query(1,1,n))%=P; 
            x = fa[tx];    
        }
        else {
            ql = ID[ty], qr = ID[y];
            (ret += query(1,1,n))%=P;
            y = fa[ty];    
        }
    }

    if(x == y) {
        ql = ID[x],qr = ql;
        (ret += query(1,1,n))%=P;
        return ret;
    }
     if(deep[x] > deep[y]) swap(x,y);
    ql = ID[x], qr = ID[y]; 
     (ret += query(1,1,n))%=P;
  return ret;
}

void LCA_add(int x,int y,int k) {
    qa = k%P;
    while(tx != ty) {
        if(deep[tx] >= deep[ty]) {
            //x 走到 top[x]（编号小） 的 爸爸 ,top[x] 的爸爸是轻链 
            ql = ID[tx], qr = ID[x];//下闭上开 
            update(1,1,n); 
            x = fa[tx];    
        }
        else {
            ql = ID[ty], qr = ID[y];
            update(1,1,n);
            y = fa[ty];    
        }
    }

    if(x == y) {
        ql = ID[x],qr = ql;
        update(1,1,n);
        return;
    }
     if(deep[x] > deep[y]) swap(x,y);
    ql = ID[x], qr = ID[y]; 
     update(1,1,n);
}

int main() {
    scanf("%d %d %d %d",&n, &m, &root, &P);
    for(int i = 1;i <= n;i++) scanf("%d",A+i);
    for(int i = 1,x,y;i < n;i++) {
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }

    dfs1(root,1);
    dfs2(root);
    build(1,1,n);

    for(int i = 1,x,l,r,z;i <= m;i++) {
        scanf("%d",&x);
        if(x == 1) {
            scanf("%d%d%d",&l,&r,&z);
            LCA_add(l,r,z);
        } else if(x == 2) {
            scanf("%d%d",&l,&r);
            printf("%d
",LCA(l,r));
        } else if(x == 3) {
            scanf("%d%d",&l,&z);
            ql = ID[l],qr = ql+num[l]-1,qa=z;
            update(1,1,n);
        } else {
            scanf("%d",&z);
            ql = ID[z],qr = ql + num[z]-1;
            printf("%d
",query(1,1,n));
        }
    }
    return 0;
}