树链剖分模板，当然是轻重链剖分。

我用带懒惰标记的线段树。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll vet[200005], head[100005], nxt[200005], num, cost[100005], numa,
    deep[100005], fa[100005], size[100005], top[100005], tree[400005], 
    tag[400005], pos[100005], a[100005], son[100005], q, n, m, R, P, x, y, z;
void add(ll u, ll v){
    num ++;
    vet[num] = v;
    nxt[num] = head[u];
    head[u]  = num;
}
void dfs(ll u, ll fat, ll dep){
    deep[u] = dep;
    fa[u] = fat;  
    size[u] = 1;
    ll maxson = 0, sonn = 0;
    for(int i = head[u]; i; i = nxt[i]){
        ll v = vet[i];
        if(v == fat) continue;
        dfs(v, u, dep+1);
        size[u] += size[v];
        if(size[v] > maxson){
            maxson = size[v];
            sonn = v;
        }
    }
    son[u] = sonn;
}
void DFS(ll u, ll fat, ll number){
    top[u] = number;
    numa ++; 
    a[numa] = cost[u];
    pos[u] = numa;
    if(son[u] == 0) return;
    DFS(son[u], u, number);
    for(int i = head[u]; i; i = nxt[i]){
        ll v = vet[i];
        if(v == fat || v == son[u]) continue;
        DFS(v, u, v);
    }
}
void maketree(ll p, ll l, ll r){
    if(l == r){
        tree[p] = a[l] % P;
        return;
    }
    ll mid = l + (r-l)/2;
    maketree(p+p, l, mid);
    maketree(p+p+1, mid+1, r);
    tree[p] = tree[p+p] + tree[p+p+1];
    tree[p] %= P;
}
void pushdown(ll p, ll l, ll r){
    ll mid = l + (r-l)/2;
    if(tag[p] > 0 && l != r){
        tree[p+p] += (mid - l + 1) * tag[p] % P;  tag[p+p] += tag[p] % P;
        tree[p+p+1] += (r - mid) * tag[p] % P;  tag[p+p+1] += tag[p] % P;
        tag[p+p] %= P; tag[p+p+1] %= P;
        tag[p] = 0;
    }
}
void add(ll p, ll l, ll r, ll x, ll y, ll z){
    pushdown(p, l, r);
    if(l == x && r == y){
        tree[p] += (r-l+1) * z % P;
        tag[p] += z % P;
        return;
    }
    ll mid = l + (r-l)/2;
    if(x > mid) add(p+p+1, mid+1, r, x, y, z);
    else if(y <= mid) add(p+p, l, mid, x, y, z);
    else {
        add(p+p, l, mid, x, mid, z);
        add(p+p+1, mid+1, r, mid+1, y, z);
    }
    tree[p] = tree[p+p] + tree[p+p+1];
    tree[p] %= P;
}
ll acc(ll p, ll l, ll r, ll x, ll y){
    pushdown(p, l, r);
    if(l == x && r == y){
        tree[p] %=  P;
        return tree[p] % P;
    }
    ll mid = l + (r-l)/2;
    if(x > mid) return acc(p+p+1, mid+1, r, x, y);
    else if(y <= mid) return acc(p+p, l, mid, x, y);
    else return acc(p+p, l, mid, x, mid) + acc(p+p+1, mid+1, r, mid+1, y);
}
void change(ll u, ll v, ll c){
    c %= P;
    while(top[u] != top[v]){
        if(deep[top[u]] < deep[top[v]]) swap(u, v);
        add(1, 1, n, pos[top[u]], pos[u], c);
        u = fa[top[u]];
    }
    if(deep[u] < deep[v]) swap(u, v);
        add(1, 1, n, pos[v], pos[u], c);
}
ll find(ll u, ll v){
    ll an = 0;
    while(top[u] != top[v]){
        if(deep[top[u]] < deep[top[v]]) swap(u, v);
        an += acc(1, 1, n, pos[top[u]], pos[u]);
        an %= P;
        u = fa[top[u]];
    }
    if(deep[u] < deep[v]) swap(u, v);
    an += acc(1, 1, n, pos[v], pos[u]);
    return an % P;
}
int main(){
    scanf("%lld%lld%lld%lld", &n, &m, &R, &P);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &cost[i]);
        cost[i] = cost[i] % P;
    }
    for(int i = 1; i < n; i++){
        scanf("%lld%lld", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(R, 0, 1);
    DFS(R, 0, R);
//    for(int i = 1; i <= n; i++)
//        printf("%lld ", top[i]);
    maketree(1, 1, n);
    for(int i = 1; i <= m; i++){
        scanf("%lld", &q);
        if(q == 1){
            scanf("%lld%lld%lld", &x, &y, &z);
            change(x, y, z % P);
        }else if(q == 2){
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", find(x, y));
        }else if(q == 3){
            scanf("%lld%lld", &x, &z);
            add(1, 1, n, pos[x], pos[x] + size[x] - 1, z % P);
        }else{
            scanf("%lld", &x);
            printf("%lld\n", acc(1, 1, n, pos[x], pos[x] + size[x] - 1));
        }
    }
    return 0;
}