37分树剖求调

马蜂清爽

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,r,p,u,v,op,k,cnt;
int a[100001],fa[100001],dep[100001],siz[100001],w[100001];
int top[100001],dfn[100001];
int sum[1000001],tag[1000001];
vector<int> e[100001];
void dfs1(int u){
    siz[u]=1;
    dfn[u]=++cnt;
    w[cnt]=a[u];
    for (int v:e[u]){
        if (v==fa[u]){
            continue;
        }
        dep[v]=dep[u]+1;
        fa[v]=u;
        dfs1(v);
        siz[u]+=siz[v];
    }
}
void dfs2(int u,int t){
    int p=0;
    top[u]=t;
    for (int v:e[u]){
        if (v==fa[u]){
            continue;
        }
        if (siz[v]>siz[p]){
            p=v;
        }
    }
    if (!p){
        return;
    }
    dfs2(p,t);
    for (int v:e[u]){
        if (v==fa[u]||v==p){
            continue;
        }
        dfs2(v,v);
    }
}
void pushdown(int l,int r,int mid,int k){
    tag[k<<1]+=tag[k];
    tag[k<<1|1]+=tag[k];
    sum[k<<1]+=tag[k]*(mid-l+1);
    sum[k<<1|1]+=tag[k]*(r-mid);
    tag[k<<1]%=p;
    tag[k<<1|1]%=p;
    sum[k<<1]%=p;
    sum[k<<1|1]%=p;
    tag[k]=0;
}
void modify(int l,int r,int k,int a,int b,int m){
    if (r<a||l>b){
        return;
    }
    if (l>=a&&r<=b){
        tag[k]+=m;
        sum[k]+=m*(r-l+1);
        tag[k]%=p;
        sum[k]%=p;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(l,r,mid,k);
    modify(l,mid,k<<1,a,b,m);
    modify(mid+1,r,k<<1|1,a,b,m);
    sum[k]=(sum[k<<1]+sum[k<<1|1])%p;
}
int query(int l,int r,int k,int a,int b){
    if (l>b||r<a){
        return 0;
    }
    if (l>=a&&r<=b){
        return sum[k];
    }
    int mid=(l+r)>>1;
    pushdown(l,r,mid,k);
    return (query(l,mid,k<<1,a,b)+query(mid+1,r,k<<1|1,a,b))%p;
}
void build(int l,int r,int k){
    if (l==r){
        sum[k]=w[l]%p;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,k<<1);
    build(mid+1,r,k<<1|1);
    sum[k]=(sum[k<<1]+sum[k<<1|1])%p;
}
void add(int u,int v,int k){
    while (top[u]!=top[v]){
        if (dep[v]>dep[u]){
            swap(u,v);
        }
        modify(1,n,1,dfn[top[u]],dfn[u],k);
        u=fa[top[u]];
    }
    if (dep[v]>dep[u]){
        swap(u,v);
    }
    modify(1,n,1,dfn[v],dfn[u],k);
}
int qry(int u,int v){
    int ans=0;
    while (top[u]!=top[v]){
        if (dep[v]>dep[u]){
            swap(u,v);
        }
        ans=(ans+query(1,n,1,dfn[top[u]],dfn[u]))%p;
        u=fa[top[u]];
    }
    if (dep[v]>dep[u]){
        swap(u,v);
    }
    ans=(ans+query(1,n,1,dfn[v],dfn[u]))%p;
    return ans;
}
signed main(){
    cin>>n>>m>>r>>p;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    for (int i=1;i<n;i++){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(r);
    dfs2(r,r);
    build(1,n,1);
    while (m--){
        cin>>op>>u;
        if (op==1){
            cin>>v>>k;
            add(u,v,k);
        }else if (op==2){
            cin>>v;
            cout<<qry(u,v)<<endl;
        }else if (op==3){
            cin>>k;
            modify(1,n,1,dfn[u],dfn[u]+siz[u]-1,k);
        }else{
            cout<<query(1,n,1,dfn[u],dfn[u]+siz[u]-1)<<endl;
        }
    }
    return 0;
}