树剖求调，只 AC #1#3#11【悬关】

rt，28pts，AC #1#3#11，其余 WA

线段树应该是没问题的，我直接从线段树模板题 AC 代码里复制过来的，我估计是树剖和 main 函数里写错了，但是找不到

悬一关，求求大佬们了

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
#define int long long
int in()
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=1e5+10;
int a[N],mod;
#define lc (x<<1)
#define rc ((x<<1)|1)
struct nod
{
    int l,r,lazy,val;
};
struct SEG
{
    nod tree[N<<2];
    void pushup(int x)
    {
        tree[x].val=(tree[lc].val+tree[rc].val)%mod;
    }
    void pushdown(int x)
    {
        tree[lc].val=(tree[lc].val+tree[x].lazy*(tree[lc].r-tree[lc].l+1))%mod;
        tree[lc].lazy=(tree[lc].lazy+tree[x].lazy)%mod;
        tree[rc].val=(tree[rc].val+tree[x].lazy*(tree[rc].r-tree[rc].l+1))%mod;
        tree[rc].lazy=(tree[rc].lazy+tree[x].lazy)%mod;
        tree[x].lazy=0;
    }
    void build(int x,int l,int r)
    {
        tree[x].l=l,tree[x].r=r;
        if(l==r)
        {
            tree[x].val=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(lc,l,mid),build(rc,mid+1,r);
        pushup(x);
    }
    void change(int x,int l,int r,int c)
    {
        if(tree[x].l==l&&tree[x].r==r)
        {
            tree[x].val=(tree[x].val+c*(r-l+1))%mod;
            tree[x].lazy=(tree[x].lazy+c)%mod;
            return;
        }
        int mid=(tree[x].l+tree[x].r)>>1;
        pushdown(x);
        if(l<=mid)change(lc,l,min(mid,r),c);
        if(r>=mid+1)change(rc,max(mid+1,l),r,c);
        pushup(x);
    }
    int query(int x,int l,int r)
    {
        if(tree[x].l==l&&tree[x].r==r)return tree[x].val;
        int mid=(tree[x].l+tree[x].r)>>1,ans=0;
        pushdown(x);
        if(l<=mid)ans=(ans+query(lc,l,min(mid,r)))%mod;
        if(r>=mid+1)ans=(ans+query(rc,max(mid+1,l),r))%mod;
        return ans;
    }
}T;
namespace cut_tree
{
    vector<int>e[N];
    int son[N],siz[N],dep[N],fa[N],val[N];
    void build(int u)
    {
        son[u]=-1,siz[u]=1;
        for(int v:e[u])
            if(!dep[v])
            {
                dep[v]=dep[u]+1,fa[v]=u;
                build(v);
                siz[u]+=siz[v];
                if(son[u]==-1||siz[v]>siz[son[u]])son[u]=v;
            }
    }
    int rnk[N],dfn[N],top[N],cnt=0;
    void cut(int u,int t)
    {
        top[u]=t,dfn[u]=++cnt,rnk[cnt]=u,a[cnt]=val[u];
        if(son[u]==-1)return;
        cut(son[u],t);
        for(int v:e[u])
            if(v!=son[u]&&v!=fa[u])cut(v,v);
    }
    void init(int s)
    {
        dep[s]=1,build(s),cut(s,s);
    }
    int sum(int u,int v)
    {
        int tot=0;
        while(top[u]!=top[v])
        {
            if(dep[top[u]]<dep[top[v]])swap(u,v);
            tot=(tot+T.query(1,dfn[top[u]],dfn[u]))%mod;
            u=fa[top[u]];
        }
        if(dep[u]<dep[v])swap(u,v);
        return (tot+T.query(1,dfn[v],dfn[u]))%mod;
    }
    void add(int u,int v,int z)
    {
        while(top[u]!=top[v])
        {
            if(dep[top[u]]<dep[top[v]])swap(u,v);
            T.change(1,dfn[top[u]],dfn[u],z);
            u=fa[top[u]];
        }
        if(dep[u]<dep[v])swap(u,v);
        T.change(1,dfn[v],dfn[u],z);
    }
}
using namespace cut_tree;
signed main()
{
    int n=in(),q=in(),s=in();
    mod=in();
    for(int i=1;i<=n;i++)val[i]=in();
    for(int i=1;i<n;i++)
    {
        int u=in(),v=in();
        e[u].push_back(v),e[v].push_back(u);
    }
    init(s);
    T.build(1,1,n);
    while(q--)
    {
        int c=in(),x=in();
        if(c==1)
        {
            int y=in(),z=in()%mod;
            add(x,y,z);
        }
        else if(c==2)
        {
            int y=in();
            out(sum(x,y)),putchar('\n');
        }
        else if(c==3)
        {
            int z=in()%mod;
            T.change(1,dfn[x],dfn[x]+siz[x]-1,z);
        }
        else out(sum(x,rnk[dfn[x]+siz[x]-1])),putchar('\n');
    }
    return 0;
}