星感代码在线求条 | 19 pts 未过样例

Submission

样例输出：

0
17

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,rt;
ll mod,a[N];
vector<int> g[N];
int fa[N],wc[N],siz[N],top[N],dfn[N],rdfn[N],dep[N],cnt;
void dfs1(int u,int father) {
    fa[u]=father;
    siz[u]=1;
    dep[u]=dep[father]+1;
    for(int v:g[u]) {
        if(v!=father) {
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[wc[u]]) wc[u]=v;
        }
    }
}
void dfs2(int u,int t0p) {
    dfn[u]=++cnt;
    rdfn[cnt]=u;
    top[u]=t0p;
    if(wc[u]) {
        dfs2(wc[u],t0p);
        for(int v:g[u])
            if(v!=fa[u]&&v!=wc[u]) dfs2(v,v);
    }
}
struct node {
    int l,r;
    ll sum,add;
    int getmid() {
        return (l+r)/2;
    }
} tr[N*4];
int ls(int p) {
    return p*2;
}
int rs(int p) {
    return p*2+1;
}
void pushup(int p) {
    tr[p].sum=(tr[ls(p)].sum+tr[rs(p)].sum)%mod;
}
void build(int p,int l,int r) {
    tr[p].l=l,tr[p].r=r;
    if(l==r) {
        tr[p].sum=a[rdfn[l]]%mod;
        return;
    }
    int mid=(l+r)/2;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    pushup(p);
}
void pushdown(int p) {
    (tr[ls(p)].sum+=tr[p].add*(tr[ls(p)].r-tr[ls(p)].l+1))%=mod;
    (tr[rs(p)].sum+=tr[p].add*(tr[rs(p)].r-tr[rs(p)].l+1))%=mod;
    (tr[ls(p)].add+=tr[p].add)%=mod;
    (tr[rs(p)].add+=tr[p].add)%=mod;
    tr[p].add=0;
}
void update(int p,int l,int r,ll k) {
    if(l<=tr[p].l&&r>=tr[p].r) {
        (tr[p].sum+=k*(tr[p].r-tr[p].l+1))%=mod;
        (tr[p].add+=k)%=mod;
        return;
    }
    int mid=tr[p].getmid();
    if(l<=mid) update(ls(p),l,r,k);
    if(r>mid) update(rs(p),l,r,k);
    pushup(p);
}
int query(int p,int l,int r) {
    if(l<=tr[p].l&&r>=tr[p].r) return tr[p].sum;
    int mid=tr[p].getmid(),res=0;
    if(l<=mid) (res+=query(ls(p),l,r))%=mod;
    if(r>mid) (res+=query(rs(p),l,r))%=mod;
    return res;
}
void upd(int x,int y,ll z) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        update(1,dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    update(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),z);
}
int qry(int x,int y) {
    int ans=0;
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        (ans+=query(1,dfn[top[x]],dfn[x]))%=mod;
        x=fa[top[x]];
    }
    (ans+=query(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y])))%=mod;
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>rt>>mod;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,u,v;i<n;i++) {
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(rt,0);
    dfs2(rt,rt);
    // for(int i=1;i<=n;i++) cout<<dfn[i]<<' ';cout<<'\n';
    // for(int i=1;i<=n;i++) cout<<fa[i]<<' ';cout<<'\n';
    // for(int i=1;i<=n;i++) cout<<top[i]<<' ';cout<<'\n';
    // for(int i=1;i<=n;i++) cout<<siz[i]<<' ';cout<<'\n';
    build(1,1,n);
    for(int i=1,op,x,y,z;i<=m;i++) {
        cin>>op;
        if(op==1) {
            cin>>x>>y>>z;
            upd(x,y,z%mod);
        }
        else if(op==2) {
            cin>>x>>y;
            cout<<qry(x,y)<<'\n';
        }
        else if(op==3) {
            cin>>x>>y;
            update(1,dfn[x],dfn[x]+siz[x]-1,y%mod);
        }
        else {
            cin>>x;
            cout<<query(1,dfn[x],dfn[x]+siz[x]-1)<<'\n';
        }
        // cout<<query(1,dfn[rt],dfn[rt]+siz[rt]-1)<<'\n';
    }
    return 0;
}