萌新袜子刚学 CSP 19pts 求调

AC on #3,#11\ MLE on #1,#6,#9\ WA on #2,#4,#5,#6,#7,#8,#10

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
#define int ll
#define itn int
#define umap unordered_map
#define uset unordered_set
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back

using namespace std;

const int inf = 0x3f3f3f3f; 
const int maxn = 1e5 + 7;

int dep[maxn], fa[maxn], top[maxn], hson[maxn], siz[maxn], dfn[maxn], rnk[maxn];
int tot;
int n, m, root, mod;
vector<int> G[maxn];
int d[maxn * 4], b[maxn * 4];
int num[maxn];

inline void dfs1(int u){
    hson[u] = -1;
    siz[u] = 1;
    for(auto v : G[u]){
        if(!dep[v]){
            dep[v] = dep[u] + 1, fa[v] = u;
            dfs1(v);
            siz[u] += siz[v];
            if(hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v;
        }
    }
} 

inline void dfs2(int u, int f){
    top[u] = f;
    dfn[u] = ++tot;
    rnk[tot] = u;
    if(hson[u] == -1)
        return;
    dfs2(hson[u], f);
    for(auto v : G[u])
        if(v != hson[u] && v != fa[u])
            dfs2(v, v); 
}

inline void build(int l, int r, int p){
    if(l == r){
        d[p] = num[rnk[l]] % mod;
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(l, mid, p << 1),
    build(mid + 1, r, (p << 1) | 1);
    d[p] = (d[p << 1] + d[(p << 1) | 1]) % mod;
}

inline void pd(int s, int t, int p){
    int l = (p << 1), r = (p << 1) | 1, mid = (s + t) >> 1;
    if(b[p]){
        b[p << 1] += b[p];
        b[(p << 1) | 1] += b[p];
        d[p << 1] = (d[p << 1] + b[p] * (mid - s + 1)) % mod;
        d[(p << 1) | 1] = (d[(p << 1) | 1] + b[p] * (t - mid)) % mod;
    }
}

inline void update(int l,int r,int c,int s,int t,int p){
    if(l <= s && t <= r){
        d[p] += (t - s + 1) * c,b[p] += c;
        return;
    }
    int m = s + ((t - s) >> 1);
    pd(s, t, p);
    if(l <= m) update(l, r, c, s, m, p << 1);
    if(r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
    d[p] = (d[p << 1] + d[(p << 1) | 1]) % mod;
}

inline int getsum(int l,int r,int s,int t,int p){
    if(l <= s && t <= r)
        return d[p] % mod;
    int m = s + ((t - s) >> 1);
    int sum = 0;
    pd(s, t, p);
    if(l <= m) sum = (sum + getsum(l, r, s, m, p << 1)) % mod;
    if(r > m) sum = (sum + getsum(l, r, m + 1, t, (p << 1) | 1)) % mod;
    return sum;
}

inline void upd(int s, int t, int c){
    c %= mod;
    while(top[s] != top[t]){
        if(dep[top[s]] < dep[top[t]]) 
            swap(s, t);
        update(dfn[top[s]], dfn[s], c, 1, n, 1);
        s = fa[top[s]];
    }
    if(dep[s] > dep[t])
        swap(s, t);
    update(dfn[s], dfn[t], c, 1, n, 1);
}

inline int get(int s, int t){
    int ret = 0;
    while(top[s] != top[t]){
        if(dep[top[s]] < dep[top[t]])
            swap(s, t);
        ret = (ret + getsum(dfn[top[s]], dfn[s], 1, n, 1)) % mod;
        s = fa[top[s]];
    }
    if(dep[s] > dep[t])
        swap(s, t);
    ret = (ret + getsum(dfn[s], dfn[t], 1, n, 1)) % mod;
    return ret;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> root >> mod;
    F(i, 1, n)
        cin >> num[i];
    F(i, 1, n - 1){
        int u, v;
        cin >> u >> v;
        G[u].pb(v), G[v].pb(u);
    }
    dfs1(root);
    dfs2(root, 0);
    build(1, n, 1);
    while(m--){
        int op;
        cin >> op;
        if(op == 1){
            int x, y, z;
            cin >> x >> y >> z;
            upd(x, y, z);
        }
        else if(op == 2){
            int x, y;
            cin >> x >> y;
            cout << get(x, y) << '\n';
        }
        else if(op == 3){
            int x, y;
            cin >> x >> y;
            update(dfn[x], dfn[x] + siz[x] - 1, y, 1, n, 1);
        } 
        else if(op == 4){
            int x;
            cin >> x;
            cout << getsum(dfn[x], dfn[x] + siz[x] - 1, 1, n, 1) << '\n';
        }
    }

    return 0;
}