萌新刚学树剖114514秒，9pts求助

rt

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

struct EDGE{
    int to,next;
}e[100005<<1|1];
int n,m,r,mod,cnt,head[100005],a[100005];
int dep[100005],sum[100005],f[100005];
int id[100005],top[100005],son[100005],seg[100005],segcnt=0;
inline void add_edge(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

void dfs1(int now,int fa){
    f[now]=fa;
    dep[now]=dep[fa]+1;
    sum[now]=1;
    for(int i=head[now];i;i=e[i].next){
        if(e[i].to==fa)
            continue;
        dfs1(e[i].to,now);
        sum[now]+=sum[e[i].to];
        if(sum[son[now]]<sum[e[i].to])
            son[now]=e[i].to;
    }
}
void dfs2(int now,int t){
    top[now]=t;
    seg[id[now]=++segcnt]=now;
    if(!son[now])
        return;
    dfs2(son[now],t);
    for(int i=head[now];i;i=e[i].next)
        if(e[i].to!=f[now]&&e[i].to!=son[now])
            dfs2(e[i].to,e[i].to);
}

struct TREE{
    int l,r,v;
}t[100005<<2|1];
inline void pushup(int x){
    t[x].v=(t[x<<1].v+t[x<<1|1].v)%mod;
}
void bt(int l,int r,int x){
    t[x].l=l,t[x].r=r;
    if(l==r){
        t[x].v=a[seg[l]];
        return;
    }
    int mid=(l+r)>>1;
    bt(l,mid,x<<1);
    bt(mid+1,r,x<<1|1);
    pushup(x);
}
int query(int l,int r,int x){
    if(l<=t[x].l&&t[x].r<=r)
        return t[x].v;
    int mid=(t[x].l+t[x].r)>>1,ans=0;
    if(l<=mid)
        ans=(ans+query(l,r,x<<1))%mod;
    if(mid<r)
        ans=(ans+query(l,r,x<<1|1))%mod;
    return ans;
}
void upd(int l,int r,int x,int w){
    if(l<=t[x].l&&t[x].r<=r)
        return (void)(t[x].v=(t[x].v+w)%mod);
    int mid=(t[x].l+t[x].r)>>1;
    if(l<=mid)
        upd(l,r,x<<1,w);
    if(mid<r)
        upd(l,r,x<<1|1,w);
    pushup(x);
}

void op1(int x,int y,int z){
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    if(top[x]==top[y])
        return (void)upd(min(id[x],id[y]),max(id[x],id[y]),1,z);
    upd(id[top[x]],id[x],1,z);
    op1(f[top[x]],y,z);
}
int op2(int x,int y){
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    if(top[x]==top[y])
        return query(min(id[x],id[y]),max(id[x],id[y]),1);
    return (query(id[top[x]],id[x],1)+op2(f[top[x]],y))%mod;
}
inline void op3(int x,int z){
    upd(id[x],id[x]+sum[x]-1,1,z);
}
inline int op4(int x){
    return query(id[x],id[x]+sum[x]-1,1);
}

int main(){
    scanf("%d%d%d%d",&n,&m,&r,&mod);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    for(int i=1,u,v;i<n;i++)
        scanf("%d%d",&u,&v),add_edge(u,v),add_edge(v,u);
    dfs1(r,r);
    dfs2(r,r);
    bt(1,segcnt,1);
    for(int i=1,op,x,y,z;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&x,&y,&z);
            op1(x,y,z);
        }else if(op==2){
            scanf("%d%d",&x,&y);
            printf("%d\n",op2(x,y));
        }else if(op==3){
            scanf("%d%d",&x,&z);
            op3(x,z);
        }else{
            scanf("%d",&x);
            printf("%d\n",op4(x));
        }
    }
    return 0;
}