树剖板子题求调玄关

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n,m,r,P;
int a[N];

struct edge{
    int v,nxt;
}e[N*2];
int head[N],cnt=2;
void add(int u,int v){
    e[cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}

int dep[N],fa[N],son[N],siz[N];
int w[N],dfn[N],top[N],num=0;

void dfs1(int u,int fat){
    dep[u]=dep[fat]+1;
    fa[u]=fat;
    siz[u]=1;
    int mx=-1;
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].v==fat)continue;
        dfs1(e[i].v,u);
        siz[u]+=siz[e[i].v];
        if(siz[e[i].v]>mx){
            mx=siz[e[i].v];
            son[u]=e[i].v;
        }
    }
}

void dfs2(int u,int topf){
    dfn[u]=++num;
    w[num]=a[u];
    top[u]=topf;
    if(!son[u])return;
    dfs2(son[u],topf);
    for(int i=head[u];i;i=e[i].nxt){
        if(!dfn[e[i].v])
            dfs2(e[i].v,e[i].v);
    }
}

struct node{
    int l,r;
    int val,lazy;
}t[N*4];

void pushup(int p){
    t[p].val=(t[p*2].val+t[p*2+1].val)%P;
}

void pushdown(int p){
    t[p*2].val=(t[p*2].val+(t[p*2].r-t[p*2].l-1)*t[p].lazy)%P;
    t[p*2+1].val=(t[p*2+1].val+(t[p*2+1].r-t[p*2+1].l-1)*t[p].lazy)%P;
    t[p*2].lazy=(t[p*2].lazy+t[p].lazy)%P;
    t[p*2+1].lazy=(t[p*2+1].lazy+t[p].lazy)%P;
    t[p].lazy=0;
}

void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].val=w[l]%P;
        return;
    }
    int m=l+r>>1;
    build(p*2,l,m);
    build(p*2+1,m+1,r);
    pushup(p);
}

int query(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r)return t[p].val;
    int m=t[p].l+t[p].r>>1,ans=0;
    pushdown(p);
    if(l<=m)ans=(ans+query(p*2,l,r))%P;
    if(r>m)ans=(ans+query(p*2+1,l,r))%P;
    return ans;
}

void update(int p,int l,int r,int val){
    if(l<=t[p].l&&t[p].r<=r){
        t[p].val=(t[p].val+(t[p].r-t[p].l+1)*val)%P;
        t[p].lazy=(t[p].lazy+val)%P;
        return;
    }
    int m=t[p].l+t[p].r>>1;
    pushdown(p);
    if(l<=m)update(p*2,l,r,val);
    if(r>m)update(p*2+1,l,r,val);
    pushup(p);
}

int treequery(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=(ans+query(1,dfn[top[x]],dfn[x]))%P;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans=(ans+query(1,dfn[x],dfn[y]))%P;
    return ans;
}

void treeupdate(int x,int y,int val){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,dfn[top[x]],dfn[x],val%P);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,dfn[x],dfn[y],val);
}

void treesonsupdate(int u,int val){
    update(1,dfn[u],dfn[u]+siz[u]-1,val%P);
}

int treesonsquery(int u){
    return query(1,dfn[u],dfn[u]+siz[u]-1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>r>>P;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        add(x,y),add(y,x);
    }
    dfs1(r,0);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        int op,x,y,z;
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            treeupdate(x,y,z);
        }else if(op==2){
            cin>>x>>y;
            cout<<treequery(x,y)%P<<'\n';
        }else if(op==3){
            cin>>x>>z;
            treesonsupdate(x,z);
        }else if(op==4){
            cin>>x;
            cout<<treesonsquery(x)%P<<'\n';
        }
    }
    return 0;
}