萌新28pts救命

rt

#include<bits/stdc++.h>
#define maxn int(1e5+5)
#define ll long long
using namespace std;
struct node{
    int lx, rx;
    ll ind, lazy;
} T[maxn<<2];
vector<int> e[maxn];
ll mod, a[maxn];
int n, m, rt, fa[maxn], dfn[maxn], siz[maxn], top[maxn], hv[maxn], num, rdfn[maxn], dep[maxn];
void pushup(int x) {
    T[x].ind = (T[x<<1].ind+T[(x<<1)+1].ind)%mod;
    return;
}
void pushdown(int x) {
    T[x<<1].ind+=((T[x<<1].rx-T[x<<1].lx+1)*T[x].lazy)%mod;
    T[x<<1].lazy+=T[x].lazy;
    T[(x<<1)+1].ind+=((T[(x<<1)+1].rx-T[(x<<1)+1].lx+1)*T[x].lazy)%mod;
    T[(x<<1)+1].lazy+=T[x].lazy;
    T[x].lazy = 0;
    T[x<<1].ind%=mod;
    T[(x<<1)+1].ind%=mod;
    T[x<<1].lazy%=mod;
    T[(x<<1)+1].lazy%=mod;
    return;
}
void build(int x, int l, int r) {
    if(l==r) {
        T[x].lx = T[x].rx = l;
        T[x].ind = a[rdfn[l]]%mod;
        return;
    }
    T[x].lx = l; T[x].rx = r;
    int mid = (l+r)>>1;
    build(x<<1, l, mid);
    build((x<<1)+1, mid+1, r);
    pushup(x);
    return;
}
void modify(int x, int l, int r, ll ind) {
    if(T[x].lx>=l&&T[x].rx<=r) {
        T[x].lazy+=ind; if(T[x].lazy>=mod) T[x].lazy-=mod;
        T[x].ind+=((T[x].rx-T[x].lx+1)*ind)%mod;
        return;
    }
    pushdown(x);
    int mid = (T[x].lx+T[x].rx)>>1;
    if(l <= mid) modify(x<<1, l, r, ind);
    if(r > mid) modify((x<<1)+1, l, r, ind);
    pushup(x);
    return;
}
ll query(int x, int l, int r) {
    if(T[x].lx>=l&&T[x].rx<=r) {
        return T[x].ind%mod;
    }
    pushdown(x);
    ll ret = 0; int mid = (T[x].lx+T[x].rx)>>1;
    if(l <= mid) ret += query(x<<1, l, r);
    if(r > mid) ret += query((x<<1)+1, l, r);
    return ret%mod;
}
void dfs1(int x) {
    siz[x] = 1;
    for(auto i:e[x]) {
        if(i==fa[x]) continue;
        fa[i] = x;
        dep[i] = dep[x]+1;
        dfs1(i);
        siz[x]+=siz[i];
        hv[x] = (hv[x]==0||siz[hv[x]]<siz[i])?i:hv[x];
    }
    return;
}
void dfs2(int x) {
    dfn[x] = num;
    rdfn[num] = x;
    if(hv[x]) {
        top[hv[x]] = top[x];
        num++;
        dfs2(hv[x]);
    }
    for(auto i:e[x]) {
        if(i==fa[x]||i==hv[x]) continue;
        top[i] = i;
        num++;
        dfs2(i);
    }
    return;
}
void ad(int x, int y, ll z) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]>dep[top[y]]) {
            modify(1, dfn[x], dfn[top[x]], z);
            x = fa[top[x]];
        } else {
            modify(1, dfn[y], dfn[top[y]], z);
            y = fa[top[y]];
        }
    }
    if(dep[x] > dep[y]) swap(x, y);
    modify(1, dfn[x], dfn[y], z);
    return;
}
ll qr(int x, int y) {
    ll ret = 0;
    while(top[x]!=top[y]) {
        if(dep[top[x]]>dep[top[y]]) {
            ret+=query(1, dfn[x], dfn[top[x]]);
            x = fa[top[x]];
        } else {
            ret+=query(1, dfn[y], dfn[top[y]]);
            y = fa[top[y]];
        }
    }
    if(dep[x]>dep[y]) swap(x, y);
    ret+=query(1, dfn[x], dfn[y]);
    return ret;
}
//void outp(auto *a) {
//  for(int i = 1; i <= n; i++) cout << a[i] << ' ';
//  cout << endl;
//}
int main() {
    freopen("P3384_2.in", "r", stdin);
    scanf("%d%d%d%lld", &n,&m,&rt,&mod);
    int t1, t2;
    ll t3;
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &t1,&t2);
        e[t1].push_back(t2);
        e[t2].push_back(t1);
    }
    fa[rt] = rt; top[rt] = rt; num = 1; dep[rt] = 0;
    dfs1(rt);
//  outp(fa); outp(siz); outp(hv);
    dfs2(rt);
//  outp(dfn); outp(top); outp(rdfn);
    build(1, 1, n);
//  for(int i = 1; i <= n; i++) {
//      cout << query(1, i, i) <<' ';
//  }cout << endl;
    int op;
    for(int i = 1; i <= m; i++) {
        scanf("%d", &op);
        if(op==1) {
            scanf("%d%d%lld", &t1, &t2, &t3);
            ad(t1, t2, t3%mod);
        } else if(op==2) {
            scanf("%d%d", &t1, &t2);
            printf("%lld\n", qr(t1, t2));
        } else if(op==3) {
            scanf("%d%lld", &t1, &t3);
            modify(1, dfn[t1], dfn[t1]+siz[t1]+1, t3%mod);
        } else {
            scanf("%d", &t1);
            printf("%lld\n", query(1, dfn[t1], dfn[t1]+siz[t1]-1));
        }
    }
    return 0;
}

wa on #2