MnZn妹子刚学OI 树剖代码求调

#include<bits/stdc++.h> 
using namespace std;
#define N 200001
int w[N];
int n,m,p,s;
struct node{
    int to,next;
}edge[N];
int head[N],ccnt;
inline void add(int u,int v)
{
    edge[++ccnt].next=head[u];
    edge[ccnt].to=v;
    head[u]=ccnt;
}
int dep[N],son[N],f[N],siz[N];
void dfs1(int u,int fa)
{
    dep[u]=dep[fa]+1;
    f[u]=fa;
    siz[u]=1;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
int top[N],rk[N],id[N],nw[N];
int cnt;
void dfs2(int u,int t)
{
    top[u]=t,id[u]=++cnt,nw[cnt]=w[u];
    if(!son[u])return ;
    dfs2(son[u],t);
//  rk[cnt]=u;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==son[u]||v==f[u])continue;
        dfs2(v,v);
    }
}
class wme{
    private:
        struct nodee
        {
            int num,lazy;
        }tr[N<<2];
    public:
        #define lid now<<1
        #define rid now<<1|1
        void build(int now,int l,int r)
        {
            if(l==r)
            {
                tr[now].num=nw[r];
                return ;
            }
            int mid=(l+r)>>1;
            build(lid,l,mid),build(rid,mid+1,r);
            tr[now].num=(tr[lid].num+tr[rid].num)%p;
        }
        void Add(int now,int l,int r,int k)
        {
            tr[now].num+=k*(r-l+1);
            tr[now].lazy+=k;
        }
        void pushdown(int now,int l,int r)
        {
            if(!tr[now].lazy)return;
            int mid=(l+r)>>1;
            Add(lid,l,mid,tr[now].lazy);
            Add(rid,mid+1,r,tr[now].lazy);
            tr[now].lazy=0;
        }
        void upd(int now,int l,int r,int x,int y,int k)
        {
            if(x<=l&&r<=y)
            {
                Add(now,l,r,k);return ;
            }
            pushdown(now,l,r);
            int mid=(l+r)>>1;
            if(x<=mid)upd(lid,l,mid,x,y,k);
            if(y>mid) upd(rid,mid+1,r,x,y,k);
            tr[now].num=(tr[lid].num+tr[rid].num)%p;
        }
        void upd_Path(int u,int v,int k)
        {
            while(top[u]!=top[v])
            {
                if(dep[top[u]]<dep[top[v]])swap(u,v);
                upd(1,1,n,id[top[u]],id[u],k);
                u=f[top[u]];
            }
            if(dep[u]<dep[v])swap(u,v);
            upd(1,1,n,id[v],id[u],k);
        }
        void upd_Tree(int u,int k)
        {
            upd(1,1,n,id[u],id[u]+siz[u]-1,k);
        }
        long long query(int now,int l,int r,int x,int y)
        {
            if(l<=x&&r<=y) return tr[now].num;
            pushdown(now,l,r);
            int mid=(l+r)>>1;
            long long res=0;
            if(x<=mid) res+=query(lid,l,mid,x,y);
            if(y>mid) res+=query(rid,mid+1,r,x,y);
            return res%p;
        }
        long long query_Path(int u,int v)
        {
            long long res=0;
            while(top[u]!=top[v])
            {
                if(dep[top[u]]<dep[top[v]])u^=v^=u^=v;
                res+=query(1,1,n,id[top[u]],id[u]);
                u=f[top[u]];
            }res%=p;
            if(dep[u]<dep[v])u^=v^=u^=v;
            res+=query(1,1,n,id[v],id[u]);
            return res;
        }
        long long query_Tree(int u)
        {
            return query(1,1,n,id[u],id[u]+siz[u]-1);
        }
}st;

signed main()
{
    cin>>n>>m>>s>>p;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    dfs1(s,0);
    dfs2(s,s);
    st.build(1,1,n);
    while(m--)
    {
        int t,u,v,k;
        cin>>t>>u;
        if(t==1)
        {
            cin>>v>>k;
            st.upd_Path(u,v,k);
        }
        else if(t==2)
        {
            cin>>v;
            cout<<st.query_Path(u,v)%p<<endl;
        }
        else if(t==3)
        {
            cin>>k;
            st.upd_Tree(u,k);
        }
        else cout<<st.query_Tree(u)%p<<endl;
    }
    return 0;
}