重链板子求调

rt，昨天打了一遍，今天重新打只有 20pts

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
ll n, m, r, p, w[MAXN], a[MAXN], sz[MAXN], Bigson[MAXN], top[MAXN], fa[MAXN], dep[MAXN], id[MAXN], cnt;
vector <int> tr[MAXN];
struct TNode{
    ll val, tag;
}SGT[4*MAXN + 10];
void dfs1(int u, int f){
    dep[u] = dep[f] + 1; 
    fa[u] = f;
    sz[u] = 1;
    int len = tr[u].size();
    for(int i = 0; i < len; i++){
        int v = tr[u][i];
        if(v == f)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[Bigson[u]])
            Bigson[u] = v; 
    }
}
void dfs2(int u, int h){
    top[u] = h;
    id[u] = ++cnt;
    a[cnt] = w[u];
    if(Bigson[u] == 0)
        return ;
    dfs2(Bigson[u], h);
    int len = tr[u].size();
    for(int i = 0; i < len ; i++){
        int v = tr[u][i];
        if(v == fa[u] || v == Bigson[u])
            continue;
        dfs2(v, v);
    }
}
bool in(int tL, int tR, int l, int r){
    return tL >= l && tR <= r;
}
bool out(int tL, int tR, int l, int r){
    return tL > r || tR < l;
}
void pushup(int u){
    SGT[u].val = SGT[2*u].val + SGT[2*u+1].val;
    SGT[u].val %= p;
}
void makelzy(int u, int len, ll k){
    SGT[u].tag += k;
    SGT[u].val += len * k % p;
    SGT[u].tag %= p, SGT[u].val %= p;
}
void pushdown(int u, int tL, int tR){
    int mid = (tL+tR) / 2;
    makelzy(2*u, mid-tL+1, SGT[u].tag);
    makelzy(2*u+1, tR-mid, SGT[u].tag);
    SGT[u].tag = 0;
}
void build(int u, int tL, int tR){
    if(tL == tR){
        SGT[u].val = a[tL];
        return ;
    }
    int mid = (tL+tR) / 2;
    build(2*u, tL, mid);
    build(2*u+1, mid+1, tR);
    pushup(u);
}
void update(int u, int tL, int tR, int l, int r, ll k){
    if(in(tL, tR, l, r))
        makelzy(u, tL-tR+1, k);
    else if(!out(tL, tR, l, r)){
        pushdown(u, tL, tR);
        int mid = (tL+tR) / 2;
        update(2*u, tL, mid, l, r, k);
        update(2*u+1, mid+1, tR, l, r, k);
        pushup(u);
    }
}
void update_path(int u, int v, ll k){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        update(1, 1, n, id[top[u]], id[u], k);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v])
        swap(u, v);
    update(1, 1, n, id[v], id[u], k);
}
ll ask(int u, int tL, int tR, int l, int r){
    if(out(tL, tR, l, r))
        return 0;
    if(in(tL, tR, l, r))
        return SGT[u].val % p;
    pushdown(u, tL, tR);
    int mid = (tL+tR) / 2;
    ll res = ask(2*u, tL, mid, l, r)%p + ask(2*u+1, mid+1, tR, l, r)%p;
    return res % p;
}
ll ask_path(int u, int v){
    ll res = 0; 
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        res += ask(1, 1, n, id[top[u]], id[u]);
        res %= p;
        u = fa[top[u]];
    }
    if(dep[u] < dep[v])
        swap(u, v);
    res += ask(1, 1, n, id[v], id[u]);
    return res % p;
}
int main(){
    cin >> n >> m >> r >> p;
    for(int i = 1; i <= n; i++)
        cin >> w[i];
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    dfs1(r, 0);
    dfs2(r, r);
    build(1, 1, n);
    while(m--){
        ll op, x, y, z;
        cin >> op;
        switch(op){
            case 1 : {
                cin >> x >> y >> z;
                update_path(x, y, z); 
                break;
            }
            case 2 : {
                cin >> x >> y;
                cout << ask_path(x, y) << endl;
                break;
            }
            case 3 : {
                cin >> x >> z;
                update(1, 1, n, id[x], id[x] + sz[x] - 1, z);
                break;
            }
            case 4 : {
                cin >> x;
                cout << ask(1, 1, n, id[x], id[x]+sz[x] - 1) << endl;
                break;
            }
        }
    }
    return 0;
}