20Pts树剖求助

Record

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,r,mod,a[N];
int dfn[N],Index;
int fa[N],d[N],top[N];
int son[N],si[N];
vector<int>g[N];

// ---------- BIT

int t1[N],t2[N];
inline void add_in(int k,int v) {int v1=v*k;while(k<=n) t1[k]+=v,t2[k]+=v1,k+=k&-k;}
inline void add(int l,int r,int v) {add_in(l,v),add_in(r+1,-v);}
inline int sum_in(int k,int *t) {int res=0;while(k)   res+=t[k],k-=k&-k;return res;}
inline int sum(int l,int r) {return (r+1)*sum_in(r,t1)-l*sum_in(l-1,t1)-(sum_in(r,t2)-sum_in(l-1,t2));}

// ---------- init

void dfs(int v,int f) {
    d[v]=d[f]+1,si[v]=1,fa[v]=f;
    int mx=0;
    for(int i:g[v])
        if(i!=f) {
            dfs(i,v),si[v]+=si[i];
            if(mx<si[i])    son[v]=i,mx=si[i];
        }
}
void dfs2(int v,int deep) {
    dfn[v]=++Index,top[v]=deep;
    add(Index,Index,a[v]);
    if(!son[v]) return;
    dfs2(son[v],deep);
    for(int i:g[v])
        if(i!=fa[v]&&i!=son[v]) dfs2(i,i);
}

// ---------- Ê÷ÆÊ

inline void change(int u,int v,int ch) {
    while(top[u]!=top[v]) {
        if(d[top[u]]<d[top[v]]) swap(u,v);
        add(dfn[top[u]],dfn[u],ch);
        u=fa[top[u]];
    }
    if(d[u]>d[v])   swap(u,v);
    add(dfn[u],dfn[v],ch);
}
inline void changesub(int u,int ch) {add(dfn[u],dfn[u]+si[u]-1,ch);}
inline int ans(int u,int v) {
    int res=0;
    while(top[u]!=top[v]) {
        if(d[top[u]]<d[top[v]]) swap(u,v);
        res+=sum(top[u],u);res%=mod;
        u=fa[top[u]];
    }
    if(d[u]>d[v])   swap(u,v);
    res+=sum(dfn[u],dfn[v]);
    return res%mod;
}
inline int anssub(int u) {return sum(dfn[u],dfn[u]+si[u]-1)%mod;}
signed main() {
    cin>>n>>m>>r>>mod;
    for(int i=1;i<=n;++i)   cin>>a[i];
    for(int i=1;i<n;++i) {int x,y;cin>>x>>y;g[x].push_back(y),g[y].push_back(x);}
    dfs(r,0);dfs2(r,r);
    //for(int i=1;i<=n;++i)   add(dfn[i],dfn[i],a[i]);
    while(m--) {
        int opt,x,y,z;
        cin>>opt>>x;
        if(opt==1) {
            cin>>y>>z;
            change(x,y,z);
        } else if(opt==2) {
            cin>>y;
            cout<<ans(x,y)<<endl;
        } else if(opt==3) {
            cin>>z;
            changesub(x,z);
        } else  cout<<anssub(x)<<endl;
    }
    return 0;
}