28pts求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') 
        {
            f=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9') 
    {
        x=(x<<1)+(x<<3)+c-48;
        c=getchar();
    }
    return x*f;
}
void write(int x)
{
    static int st[35],top=0;
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    do
    {
        st[top++]=x%10;
        x/=10;
    }while(x);
    while(top)
    {
        putchar(st[--top]+48);
    }
    puts("");
}
int n,q,r,mod,a[200010],f[200010],dep[200010],sz[200010],hs[200010];
int dfn[200010],top[200010],rnk[200010],cnt;
int he[400010],nxt[400010],vtx[400010],idx;
struct node
{
    int l,r,lz,sum;
}tr[1000010];
void add(int x,int y)
{
    idx++;
    nxt[idx]=he[x];
    he[x]=idx;
    vtx[idx]=y;
}
void dfs1(int x,int fa)
{
    hs[x]=-1;
    sz[x]=1;
    for(int i=he[x];i;i=nxt[i])
    {
        int j=vtx[i];
        if(j!=fa)
        {
            f[j]=x;
            dep[j]=dep[x]+1;
            dfs1(j,x);
            sz[x]+=sz[j];
            if(hs[x]==-1||sz[j]>sz[hs[x]])
            {
                hs[x]=j;
            }
        }
    }
}
void dfs2(int x,int tp)
{
    dfn[x]=++cnt;
    rnk[cnt]=x;
    top[x]=tp;
    if(hs[x]==-1)
    {
        return;
    }
    dfs2(hs[x],tp);
    for(int i=he[x];i;i=nxt[i])
    {
        int j=vtx[i];
        if(j!=f[x]&&j!=hs[x])
        {
            dfs2(j,j);
        }
    }
}
void build(int u,int l,int r)
{
    tr[u].l=l;
    tr[u].r=r;
    if(l==r)
    {
        tr[u].sum=a[rnk[l]];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pd(int u)
{
    if(tr[u].lz!=0)
    {
        tr[u<<1].lz+=tr[u].lz;
        tr[u<<1|1].lz+=tr[u].lz;
        int mid=tr[u].l+tr[u].r>>1;
        tr[u<<1].sum+=tr[u].lz*(mid-tr[u].l+1)%mod;
        tr[u<<1].sum%=mod;
        tr[u<<1|1].sum+=tr[u].lz*(tr[u].r-mid)%mod;
        tr[u<<1|1].sum%=mod;
        tr[u].lz=0;
    }
}
void upd(int u,int x,int y,int z)
{
    if(x<=tr[u].l&&tr[u].r<=y)
    {
        tr[u].sum=tr[u].sum+(tr[u].r-tr[u].l+1)*z%mod;
        tr[u].sum%=mod;
        tr[u].lz=z%mod;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid)
    {
        upd(u<<1,x,y,z);
    }
    if(y>mid)
    {
        upd(u<<1|1,x,y,z);
    }
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
    tr[u].sum%=mod;
}
int que(int u,int x,int y)
{
    int ans=0;
    if(x<=tr[u].l&&tr[u].r<=y)
    {
        return tr[u].sum%mod;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    pd(u);
    if(x<=mid)
    {
        ans+=que(u<<1,x,y);
        ans%=mod;
    }
    if(y>mid)
    {
        ans+=que(u<<1|1,x,y);
        ans%=mod;
    }
    return ans%mod;
}
void add_ph(int x,int y,int z)
{
    int u=x,v=y,l,r;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
        {
            swap(u,v);
        }
        l=dfn[top[u]];
        r=dfn[u];
        upd(1,l,r,z);
        u=f[top[u]];
    }
    if(dep[top[u]]>dep[top[v]])
    {
        swap(u,v);
    }
    upd(1,dfn[u],dfn[v],z);
}
int que_ph(int x,int y)
{
    int u=x,v=y,l,r,ans=0;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
        {
            swap(u,v);
        }
        l=dfn[top[u]];
        r=dfn[u];
        ans+=que(1,l,r);
        ans%=mod;
        u=f[top[u]];
    }
    if(dep[top[u]]>dep[top[v]])
    {
        swap(u,v);
    }
    ans+=que(1,dfn[u],dfn[v]);
    ans%=mod;
    return ans;
}
void add_tr(int x,int y)
{
//  puts("=============");
    int l=dfn[x],r=dfn[x]+sz[x]-1;
//  cout<<l<<" "<<r<<endl;
    upd(1,l,r,y);
}
int que_tr(int x)
{
    int l=dfn[x],r=dfn[x]+sz[x]-1;
    return que(1,l,r)%mod;
}
signed main()
{
    n=read();
    q=read();
    r=read();
    mod=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1,x,y;i<n;i++)
    {
        x=read();
        y=read();
        add(x,y);
        add(y,x);
    }
    dfs1(r,0);
    dfs2(r,r);
    build(1,1,n);
    int op,x,y,z;
    while(q--)
    {
        op=read();
        x=read();
        if(op==1)
        {
            y=read();
            z=read();
            add_ph(x,y,z);
        }
        else if(op==2)
        {
            y=read();
            write(que_ph(x,y)%mod);
        }
        else if(op==3)
        {
            y=read();
            add_tr(x,y);
        }
        else
        {
            write(que_tr(x)%mod);
        }
    }
    return 0;
}

https://www.luogu.com.cn/record/166030163