树剖

洛谷P3384，树剖板子题，树状数组维护区间操作

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll n,m,r,mod=1e9+7,cnt,v[(int)1e5+9],dep[(int)1e5+9],f[(int)1e5+9],sz[(int)1e5+9],son[(int)1e5+9],top[(int)1e5+9],id[(int)1e5+9];

vector<int> g[(int)1e5+9];

struct BIT
{
    ll a[(int)1e5 + 9],c[(int)1e5+9];
    int n;
    BIT(int x){
        n=x;
        for(int i=0;i<=n;++i)a[i]=c[i]=0;
    }
    void adda(int p,ll x)
    {
        for (; p <=n ; p += lowbit(p))
        {
            a[p] =(a[p]+x)%mod;
        }
    }
    void addc(int p,ll x)
    {
        for (; p <=n ; p += lowbit(p))
        {
            c[p] =(c[p]+x)%mod;
        }
    }

    void add(int l,int r,ll x){
        adda(l,x);
        adda(r+1,((-x)%mod+mod)%mod);
        addc(l,(l-1)*x%mod);
        addc(r+1,((r*(-x))%mod+mod)%mod);
    }

    ll qa(int p){
        ll res=0;
        for(;p;p-=lowbit(p))res=(res+a[p])%mod;
        return res;
    }
    ll qc(int p){
        ll res=0;
        for(;p;p-=lowbit(p))res=(res+c[p])%mod;
        return res;
    }

    ll query(int l,int r){
        ll res=((qa(r)*r%mod-qc(r))%mod+mod)%mod;
        res=((res-(qa(l-1)*(l-1)%mod-qc(l-1))%mod)%mod+mod)%mod;
        return res;
    }
};

void dfs1(int u,int fa,int deep){
    dep[u]=deep,f[u]=fa,sz[u]=1;
    int ma=0;
    for(auto it:g[u]){
        if(it!=fa){
            dfs1(it,u,deep+1);
            sz[u]+=sz[it];
            if(ma<sz[it]){
                ma=sz[it],son[u]=it;
            }
        }
    }
}

void dfs2(int u,int fa,BIT &tr){
    top[u]=fa,id[u]=++cnt;
    if(v[u]){
        tr.add(id[u],id[u],v[u]);
    }
    if(!son[u])return ;
    dfs2(son[u],fa,tr);
    for(auto it:g[u]){
        if(it!=son[u]&&it!=f[u]){
            dfs2(it,it,tr);
        }
    }

}

void add(int u,int v,int x,BIT &tr){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        tr.add(id[top[u]],id[u],x);
        u=f[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    tr.add(id[u],id[v],x);
}

ll query(int u,int v,BIT &tr){
    ll res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res=(res+tr.query(id[top[u]],id[u]))%mod;
        u=f[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    res+=tr.query(id[u],id[v]);
    return res%mod;
}



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>r>>mod;
    BIT b(n);
    for(int i=1;i<=n;++i)cin>>v[i];
    for(int i=1,x,y;i<n;++i){
        cin>>x>>y;
        g[x].push_back(y),g[y].push_back(x);
    }
    dfs1(r,0,1);
    dfs2(r,r,b);
    for(int i=1,opt,x,y,z;i<=m;++i){
        cin>>opt;
        if(opt==1){
            cin>>x>>y>>z;
            add(x,y,z%mod,b);
        }else if(opt==2){
            cin>>x>>y;
            cout<<query(x,y,b)<<"\n";
        }else if(opt==3){
            cin>>x>>z;
            b.add(id[x],id[x]+sz[x]-1,z%mod);
        }else {
            cin>>x;
            cout<<b.query(id[x],id[x]+sz[x]-1)<<"\n";
        }
    }
    return 0;
}