Tree Division

#include <cstdio>

#include <algorithm>

using namespace std;

struct node {
    int l, r;
    int d, lazy;
    node* ch[2];

    void push_down();
    int query(int l, int r);
    void change(int l, int r, int x);
} *root;

struct edge {
    int v;
    edge* next;
};

const int N = 100010;

int P;
int d[N], sub[N], heav[N], dep[N], top[N], f[N], id[N], revid[N];
bool vis[N];
edge* g[N];

void dfs(int u);
void dfs2(int u);
void construct_tree(node*& p, int l, int r);
void add_edge(int u, int v);
int safe_add(int x, int y);
int safe_multiply(int x, int y);
void change(int x, int y, int z);
int query(int x, int y);

int main() {
    int n, m, r, u, v, o, x, y, z;
    scanf("%d%d%d%d", &n, &m, &r, &P);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &d[i]);
        d[i] %= P;
        if (d[i] < 0)
            d[i] += P;
    }
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(r);
    dfs2(r);
    construct_tree(root, 1, n);
    while (m--) {
        scanf("%d", &o);
        switch (o) {
        case 1:
            scanf("%d%d%d", &x, &y, &z);
            z %= P;
            if (z < 0)
                x += P;
            change(x, y, z);
            break;
        case 2:
            scanf("%d%d", &x, &y);
            printf("%d\n", query(x, y));
            break;
        case 3:
            scanf("%d%d", &x, &z);
            root->change(id[x], id[x] + sub[x] - 1, z);
            break;
        case 4:
            scanf("%d", &x);
            printf("%d\n", root->query(id[x], id[x] + sub[x] - 1));
            break;
        default: break;
        }
    }
    return 0;
}

inline void add_edge(int u, int v) {
    static edge pool[N << 1];
    static int cnt;
    edge* p = pool + cnt++;
    p->v = v;
    p->next = g[u];
    g[u] = p;
}

void construct_tree(node*& p, int l, int r) {
    static node pool[N << 1];
    static int cnt;
    p = pool + cnt++;
    p->l = l;
    p->r = r;
    if (l == r) {
        p->d = d[revid[l]];
        return;
    }
    construct_tree(p->ch[0], l, (l + r) >> 1);
    construct_tree(p->ch[1], ((l + r) >> 1) + 1, r);
    p->d = safe_add(p->ch[0]->d, p->ch[1]->d);
}

void dfs(int u) {
    vis[u] = true;
    sub[u] = 1;
    for (edge* p = g[u]; p; p = p->next) {
        if (vis[p->v])
            continue;
        f[p->v] = u;
        dep[p->v] = dep[u] + 1;
        dfs(p->v);
        sub[u] += sub[p->v];
        if (sub[heav[u]] < sub[p->v])
            heav[u] = p->v;
    }
}

void dfs2(int u) {
    static int cnt;
    id[u] = ++cnt;
    revid[cnt] = u;
    if (heav[u]) {
        top[heav[u]] = top[u];
        dfs2(heav[u]);
    }
    for (edge* p = g[u]; p; p = p->next) {
        if (u != f[p->v] || p->v == heav[u])
            continue;
        top[p->v] = p->v;
        dfs2(p->v);
    }
}

inline int safe_add(int x, int y) {
    x += y;
    if (x >= P)
        return x - P;
    return x;
}

inline int safe_multiply(int x, int y)
{ return (long long)x * y % P; }

inline void node::push_down() {
    if (!lazy)
        return;
    ch[0]->lazy = safe_add(ch[0]->lazy, lazy);
    ch[1]->lazy = safe_add(ch[1]->lazy, lazy);
    d = safe_add(d, safe_multiply(lazy, r - l + 1));
    lazy = 0;
}

int node::query(int l, int r) {
    if (this->l == l && this->r == r)
        return safe_add(d, safe_multiply(lazy, r - l + 1));
    push_down();
    if (ch[0]->r >= r)
        return ch[0]->query(l, r);
    if (ch[1]->l <= l)
        return ch[1]->query(l, r);
    return safe_add(ch[0]->query(l, ch[0]->r),
                    ch[1]->query(ch[1]->l, r));
}

void node::change(int l, int r, int x) {
    if (this->l == l && this->r == r) {
        lazy = safe_add(lazy, x);
        return;
    }
    push_down();
    d = safe_add(d, safe_multiply(x, r - l + 1));
    if (ch[0]->r >= r) {
        ch[0]->change(l, r, x);
        return;
    }
    if (ch[1]->l <= l) {
        ch[1]->change(l, r, x);
        return;
    }
    ch[0]->change(l, ch[0]->r, x);
    ch[1]->change(ch[1]->l, r, x);
}

inline void change(int x, int y, int z) {
    int a = top[x], b = top[y];
    while (a != b) {
        if (dep[a] < dep[b]) {
            swap(a, b);
            swap(x, y);
        }
        root->change(id[a], id[x], z);
        x = f[a];
        a = top[x];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    root->change(id[x], id[y], z);
}

inline int query(int x, int y) {
    int a = top[x], b = top[y], ret = 0;
    while (a != b) {
        if (dep[a] < dep[b]) {
            swap(a, b);
            swap(x, y);
        }
        ret = safe_add(ret, root->query(id[a], id[x]));
        x = f[a];
        a = top[x];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    return safe_add(ret, root->query(id[x], id[y]));
}