10pts 求调

#include<bits/stdc++.h>
using namespace std;
const int N=200000+10;
int n,m,r,mod;
int e,w[N],wt[N];
int son[N],id[N],fa[N],cnt,dep[N],siz[N],top[N];
int h[N];
struct Edge{
    int to;
    int nexta;
}ed[N];
struct tree{
    int sum,lazy;
}t[N<<2];

void add(int u,int v)
{
    ed[++e].to=v;
    ed[e].nexta=h[u];
    h[u]=e;
}

void build(int p,int l,int r)
{
    if(l==r)
    {
        t[p].sum=wt[l];
        if(t[p].sum>mod) t[p].sum%mod;
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
}

void pushdown(int p,int l,int r)
{
    if(t[p].lazy)
    {
        int mid=(l+r)>>1;
        t[p<<1].lazy+=t[p].lazy;
        t[p<<1|1].lazy+=t[p].lazy;
        t[p<<1].sum+=t[p].lazy*(mid-l+1);
        t[p<<1|1].sum+=t[p].lazy*(r-mid);
        t[p<<1].sum%=mod;
        t[p<<1|1].sum%=mod;
        t[p].lazy=0;
    }
}

int ask(int p,int l,int r,int x,int y)
{
    if(x<=l && y>=r)
    {
        return t[p].sum%mod;
    }
    pushdown(p,l,r);
    int mid=(l+r)>>1;
    int res=0;
    if(x<=mid) res+=ask(p<<1,l,mid,x,y);
    if(y>=mid+1) res+=ask(p<<1|1,mid+1,r,x,y);
    return res%mod;
}

void change(int p,int l,int r,int x,int y,int k)
{
    if(l<=x && y>=r)
    {
        t[p].sum+=k*(r-l+1);
        t[p].lazy+=k;
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid) change(p<<1,l,mid,x,y,k);
    if(y>=mid+1) change(p<<1|1,mid+1,r,x,y,k);
    t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod; 
}

int qson(int x)
{
    return ask(1,1,n,id[x],id[x]+siz[x]-1);
}

void updson(int x,int k)
{
    change(1,1,n,id[x],id[x]+siz[x]-1,k);
}

int qrange(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans+=ask(1,1,n,id[top[x]],id[x]);
        ans%=mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans+=ask(1,1,n,id[x],id[y]);
    return ans%mod;
}

void updrange(int x,int y,int k)
{
    k%=mod;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        change(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    change(1,1,n,id[x],id[y],k);
}

void dfs1(int x,int f,int deep)
{
    dep[x]=deep;
    fa[x]=f;
    siz[x]=1;
    int maxson=-1;
    for(int i=h[x];i;i=ed[i].nexta)
    {
        int y=ed[i].to;
        if(y==f) continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>maxson)
        {
            son[x]=y;
            maxson=siz[y];
        }
    }
}

void dfs2(int x,int topf)
{
    id[x]=++cnt;
    wt[cnt]=w[x];
    top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x],topf);
    for(int i=h[x];i;i=ed[i].nexta)
    {
        int y=ed[i].to;
        if(y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&r,&mod);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    while(m--)
    {
        int k,x,y,z;
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            updrange(x,y,z);
        }
        else if(k==2)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",qrange(x,y));
        }
        else if(k==3)
        {
            scanf("%d%d",&x,&y);
            updson(x,y);
        }
        else
        {
            scanf("%d",&x);
            printf("%d\n",qson(x));
        }
    }
    return 0;
}