树剖求调

rt。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p,r,X=0;
const int maxn=200005;
vector<int>G[maxn];
int size[maxn];
int top[maxn];
int son[maxn];
int New[maxn];
int Old[maxn];
int fa[maxn];
int in[maxn],out[maxn];
int depth[maxn];
int A[maxn];
struct Segment{
    long long a[maxn],w[2*maxn],lzy[2*maxn];
    void pushup(int u)
    {
        w[u]=(w[u*2]+w[u*2+1])%p;
    }
    void build(int u=1,int l=1,int r=n)
    {
        if(l==r)
        {
            w[u]=a[l];
            return;
        }
        int m=(l+r)/2;
        build(u*2,l,m),build(u*2+1,m+1,r);
        pushup(u);
    }
    bool InRange(int L,int R,int l,int r)
    {
        return (l<=L)&&(R<=r);
    }
    bool OutofRange(int L,int R,int l,int r)
    {
        return (L>r)||(R<l);
    }
    void maketag(int u,int len,long long x)
    {
        lzy[u]+=x;lzy[u]%=p;
        w[u]+=len*x;w[u]%=p;
    }
    void pushdown(int u,int l,int r)
    {
        int m=(l+r)/2;
        maketag(u*2,m-l+1,lzy[u]);
        maketag(u*2+1,r-m,lzy[u]);
        lzy[u]=0;
    }
    int query(int l,int r,int u=1,int L=1,int R=n)
    {
        if(InRange(L,R,l,r)) return w[u];
        else if(!OutofRange(L,R,l,r))
        {
            int m=(L+R)/2;
            pushdown(u,L,R);
            return (query(l,r,u*2,L,m)+query(l,r,u*2+1,m+1,R))%p;
        }
        else return 0;
    }
    void update(int l,int r,long long x,int u=1,int L=1,int R=n)
    {
        if(InRange(L,R,l,r)) maketag(u,R-L+1,x);
        else if(!OutofRange(L,R,l,r))
        {
            int m=(L+R)/2;
            pushdown(u,L,R);
            update(l,r,x,u*2,L,m);
            update(l,r,x,u*2+1,m+1,R);
            pushup(u);
        }
    }
};
Segment a;
int dfs(int x,int fat)//拍成DFS序
{
    fa[x]=fat;
    size[x]=1;
    depth[x]=depth[fat]+1;
    for(int i=0;i<(int)G[x].size();i++)
    {
        if(fat!=G[x][i]) size[x]+=dfs(G[x][i],x);
        if(x!=fat&&size[G[x][i]]>size[G[x][son[x]]]) son[x]=G[x][i];//重儿子
    }
    return size[x];//子树大小
}
void Dfs(int x,int Top)//求链顶
{
    in[x]=New[x]=++X;Old[X]=x;a.a[X]=A[x];
    out[x]=in[x]+size[x]-1;
    top[x]=Top;
    if(son[x]) Dfs(son[x],Top);
    for(int i=0;i<(int)G[x].size();i++)
    {
        if(G[x][i]!=son[x]&&fa[x]!=G[x][i]) Dfs(G[x][i],G[x][i]);
    }
}
int x,y,ans;
signed main()
{
    int T;
    cin>>n>>T>>r>>p;
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int i=1;i<n;i++)
    {
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    depth[0]=0;top[r]=r;size[0]=0;
    memset(son,0,sizeof(son));
    dfs(r,0);
    Dfs(r,r);
    a.build();
    while(T--)
    {
        int op,x,y,z;
        cin>>op>>x;
        if(op==1)
        {
            cin>>y>>z;z%=p;
            while(top[x]!=top[y])
            {
                if(depth[top[x]]<depth[top[y]]) swap(x,y);
                a.update(New[top[x]],New[x],z),x=fa[top[x]];
                // cout << depth[x] << " " << depth[y] << "\n";
            }
            if(depth[x]>depth[y]) swap(x,y);
            a.update(New[x],New[y],z);
        }
        if(op==2)
        {
            ans=0;
            cin>>y;
            while(top[x]!=top[y])
            {
                if(depth[top[x]]<depth[top[y]]) swap(x,y);
                ans+=a.query(New[top[x]],New[x]),x=fa[top[x]],ans%=p;
            }
            if(depth[x]>depth[y]) swap(x,y);
            ans+=a.query(New[x],New[y]),ans%=p;
            cout<<ans%p<<endl;
        }
        if(op==3)
        {
            cin>>z;z%=p;
            a.update(in[x],out[x],z);
        }
        if(op==4)
        {
            cout<<a.query(in[x],out[x])%p<<endl;
        }
    }
}