蒟蒻求助

#include<bits/stdc++.h>
using namespace std;
#define mod p
struct Edge
{
    int fr,to;
}eg[400005];
int head[100005],edgenum;
struct SegNode
{
    int l,r,val,lazy;
}sn[800005];
struct TreeNode
{
    int fa,deep,son,id,top,size,val;
}tn[400005];
int firstw[100005],n,m,r,p;
inline void add(int fr,int to)
{
    eg[++edgenum].fr=head[fr];
    eg[edgenum].to=to;
    head[fr]=edgenum;
}
#define len(x) sn[x].r-sn[x].l+1
inline void pushup(int rt)
{
    sn[rt].val=sn[rt<<1].val+sn[rt<<1|1].val;
    sn[rt].val%=mod;
}
inline void pushdown(int rt,int len)
{
    if(sn[rt].lazy)
    {
        sn[rt<<1].lazy+=sn[rt].lazy;
        sn[rt<<1|1].lazy+=sn[rt].lazy;
        sn[rt<<1].val+=sn[rt].lazy*(len-(len>>1));
        sn[rt<<1|1].val+=sn[rt].lazy*(len>>1);
        sn[rt<<1].val%=mod;
        sn[rt<<1|1].val%=mod;
        sn[rt].lazy=0;
    }
}
inline int query(int rt,int l,int r,int fr,int to)
{
    int ans=0;
    if(fr<=l&&to>=r)
    {
        ans=sn[rt].val;
        return ans%mod;
    }
    pushdown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(fr<=mid) ans+=query(rt<<1,l,mid,fr,to);
    if(to>mid) ans+=query(rt<<1|1,mid+1,r,fr,to);
    return ans%mod;
}
inline void update(int rt,int l,int r,int fr,int to,int val)
{
    if(fr<=l&&to>=r)
    {
        sn[rt].lazy+=val;
        sn[rt].val+=val*(r-l+1);
        return;
    }
    pushdown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(fr<=mid) update(rt<<1,l,mid,fr,to,val);
    if(to>mid) update(rt<<1|1,mid+1,r,fr,to,val);
    pushup(rt);
}
inline void build(int rt,int l,int r)
{
    if(l>r) return;
    sn[rt].l=l;
    sn[rt].r=r;
    sn[rt].lazy=0;
    if(l==r)
    {
        sn[rt].val=tn[l].val;
        sn[rt].val%=mod;
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
int cnt;
inline void dfs1(int x,int fa,int deep)
{
    tn[x].deep=deep;
    tn[x].fa=fa;
    tn[x].size=1;
    int maxson=-1;
    for(int i=head[x];i;i=eg[i].fr)
    {
        if(eg[i].to==fa) continue;
        dfs1(eg[i].to,x,deep+1);
        tn[x].size+=tn[eg[i].to].size;
        if(tn[eg[i].to].size>maxson)
            maxson=tn[eg[i].to].size,tn[x].son=eg[i].to;
    }
}
inline void dfs2(int x,int top)
{
    tn[x].id=++cnt;
    tn[x].top=top;
    tn[cnt].val=firstw[x];
    if(!tn[x].son) return;
    dfs2(tn[x].son,top);
    for(int i=head[x];i;i=eg[i].fr)
    {
        if(eg[i].to==tn[x].fa||eg[i].to==tn[x].son)
            continue;
        dfs2(eg[i].to,eg[i].to);
    }
}
inline void updateroad(int x,int y,int val)
{
    val%=mod;
    while(tn[x].top!=tn[y].top)
    {
        if(tn[tn[x].top].deep<tn[tn[y].top].deep) swap(x,y);
        update(1,1,n,tn[tn[x].top].id,tn[x].id,val);
        x=tn[tn[x].top].fa;
    }
    if(tn[x].deep>tn[y].deep) swap(x,y);
    update(1,1,n,tn[x].id,tn[y].id,val);
}
inline int queryroad(int x,int y)
{
    int ans=0;
    while(tn[x].top!=tn[y].top)
    {
        if(tn[tn[x].top].deep<tn[tn[y].top].deep) swap(x,y);
        ans+=query(1,1,n,tn[tn[x].top].id,tn[x].id);
        ans%=mod;
        x=tn[tn[x].top].fa;
    }
    if(tn[x].deep>tn[y].deep) swap(x,y);
    ans+=query(1,1,n,tn[x].id,tn[y].id);
    ans%=mod;
    return ans;
}
inline int querytree(int rt)
{
    return query(1,1,n,tn[rt].id,tn[rt].id+tn[rt].size-1);
}
inline void updatetree(int rt,int k)
{
    update(1,1,n,tn[rt].id,tn[rt].id+tn[rt].size-1,k);
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i=1;i<=n;++i)
        scanf("%d",&firstw[i]);
    int a,b;
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    int op,c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&a,&b,&c);
            updateroad(a,b,c);
        }
        if(op==2)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",queryroad(a,b));
        }
        if(op==3)
        {
            scanf("%d%d",&a,&b);
            updatetree(a,b);
        }
        if(op==4)
        {
            scanf("%d",&a);
            printf("%d\n",querytree(a));
        }
    }
    return 0;
}