玩原神玩多了 树剖求调

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,m,r,p,X,Y,op,z;
const ll MAX = 3e5+10;
ll w[MAX],f[MAX],son[MAX],id[MAX],top[MAX],dep[MAX],size[MAX];
ll c1[MAX],c2[MAX];
vector <ll> edge[MAX];
namespace graph{
    void add(ll from,ll to){
        edge[from].emplace_back(to);
        edge[to].emplace_back(from);
    }
}
namespace bit{
    ll lowb1t(ll x){return x&-x;}
    void add1(ll x,ll k){
        for(int i=x;i<=n;i+=lowb1t(i)){
            c1[i]+=x;
            c2[i]+=k*x;
        }
    }
    void add(ll l,ll r,ll v){
        add1(l,v);
        add1(r+1,-v);
    }
    ll query1(ll x){
        ll res=0;
        for(int i=x;i;i-=lowb1t(i)){
            res+=c1[i]*(x+1ll);
            res-=c2[i];
        }
        return res;
    }
    ll query(ll l,ll r){return query1(r)-query1(l-1);}
}
ll cnt;
namespace dfs{
    void dfs1(ll now,ll fa){
        f[now]=fa;
        size[now]=1;
        dep[now]=dep[fa]+1;
        ll maxson=-1;
        for(auto &&e : edge[now]){
            if(e==fa) continue;
            dfs1(e,now);
            size[now]+=size[e];
            if(size[e]>maxson){
                maxson=size[e];
                son[now]=e;
            }
        }
    }
    void dfs2(ll now,ll tp){
        top[now]=tp;
        id[now]=++cnt;
        if(w[now]!=0) bit::add(id[now],id[now],w[now]);
        if(!son[now]) return ;
        dfs2(son[now],tp);
        for(auto &&e:edge[now]){
            if(e==son[now] or e==f[now]) continue;
            dfs2(e,e);
        }
    }
}
namespace oper{
    ll querypath(ll u,ll v){
        ll res=0;
    //  k%=p;
        while(top[v]!=top[u]){
            if(dep[top[u]]<dep[top[v]]) swap(u,v);
            res=(res+bit::query(id[top[u]],id[u]))%p;
            u=f[top[u]];
        }
        if(dep[u]>dep[v]) swap(u,v);
        res=(res+bit::query(id[u],id[v]))%p;
        return res%p;
    }
    void addpath(ll u,ll v,ll k){
    //  ll res=0;
            k%=p;
        while(top[v]!=top[u]){
            if(dep[top[u]]<dep[top[v]]) swap(u,v);
            bit::add(id[top[u]],id[u],k);
            u=f[top[u]];
        }
        if(dep[u]>dep[v]) swap(u,v);
        bit::add(id[u],id[v],k);
    }
    void addson(ll u,ll k){
        k%=p;
        bit::add(id[u],id[u]+size[u]-1,k);
    }
     ll queryson(ll u){
         return bit::query(id[u],id[u]+size[u]-1)%p;
     }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<n;i++){
        cin>>X>>Y;
        graph::add(X,Y);
    }
    dfs::dfs1(r,0);
    dfs::dfs2(r,r);
    while(m--){
        cin>>op>>X;
        if(op==1){
            cin>>Y>>z;
            oper::addpath(X,Y,z);
        } else if(op==2){
            cin>>Y;
            cout<<oper::querypath(X,Y)<<'\n';
        } else if(op==3){
            cin>>Y;
            oper::addson(X,Y);
        } else{
            cout<<oper::queryson(X)<<'\n';
        }
    }
    return 0;
}

我是胡桃的狗。