记录

#include <bits/stdc++.h>
using namespace std;
#define IT set<Node>::iterator
#define ls now * 2
#define rs now * 2 + 1
int n, m, cnt, last[100005], l, r, x, op, root;
long long p;
struct Edge
{
    int to, pre;
} edge[200005];
void add(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].pre = last[u];
    last[u] = cnt;
}
int idx, fa[100005], dfn[100005], dep[100005], sz[100005], zson[100005], id[100005];
long long k, val[100005], v[100005];
void dfs1(int now, int f)
{
    //cout << now << "\n";
    fa[now] = f, sz[now] = 1, dep[now] = dep[f] + 1;
    for (int i = last[now]; i; i = edge[i].pre)
    {
        int to = edge[i].to;
        if (to == f)
        {
            continue;
        }
        dfs1(to, now);
        sz[now] += sz[to];
        if (sz[to] > sz[zson[now]])
        {
            zson[now] = to;
        }
    }
}
void dfs2(int now, int top)
{
    dfn[now] = top, id[now] = ++idx, val[idx] = v[now];
    if (!zson[now])
    {
        return;
    }
    dfs2(zson[now], top);
    for (int i = last[now]; i; i = edge[i].pre)
    {
        int to = edge[i].to;
        if (to == fa[now] || to == zson[now])
        {
            continue;
        }
        dfs2(to, to);
    }
}
struct Tree
{
    int l, r;
    long long sum, tag;
} tree[400005];
void maketree(int now, int l, int r)
{
    tree[now].l = l, tree[now].r = r;
    if (l == r)
    {
        tree[now].sum = val[l];
        return;
    }
    int mid = (l + r) / 2;
    maketree(ls, l, mid), maketree(rs, mid + 1, r);
    tree[now].sum = tree[ls].sum + tree[rs].sum;
}
void pushdown(int now)
{
    if (tree[now].tag)
    {
        tree[ls].tag += tree[now].tag;
        tree[ls].tag %= p;
        tree[ls].sum += tree[now].tag % p * ((tree[ls].r - tree[ls].l + 1) % p) % p;
        tree[ls].sum %= p;
        tree[rs].tag += tree[now].tag;
        tree[rs].tag %= p;
        tree[rs].sum += tree[now].tag % p * ((tree[rs].r - tree[rs].l + 1) % p) % p;
        tree[rs].sum %= p;
        tree[now].tag = 0;
    }
}
void updata(int now, int l, int r, long long k)
{
    k %= p;
    if (l <= tree[now].l && r >= tree[now].r)
    {
        tree[now].tag = (tree[now].tag + k) % p;
        tree[now].sum = ((tree[now].r - tree[now].l + 1) % p * k + tree[now].sum) % p;
        return;
    }
    pushdown(now);
    int mid = (tree[now].l + tree[now].r) / 2;
    if (l <= mid)
    {
        updata(ls, l, r, k);
    }
    if (r > mid)
    {
        updata(rs, l, r, k);
    }
    tree[now].sum = (tree[ls].sum + tree[rs].sum) % p;
}
long long query(int now, int l, int r)
{
    //cout << tree[now].l << " " << tree[now].r << " " << l << " " << r << "\n";
    if (l <= tree[now].l && r >= tree[now].r)
    {
        return tree[now].sum % p;
    }
    pushdown(now);
    int mid = (tree[now].l + tree[now].r) / 2;
    long long ans = 0;
    if (l <= mid)
    {
        ans = (ans + query(ls, l, r)) % p;
    }
    else
    {
        ans = (ans + query(rs, l, r)) % p;
    }
    return ans % p;
}
void change(int x, int y, long long k)
{
    while (dfn[x] != dfn[y])
    {
        if (dep[dfn[x]] < dep[dfn[y]])
        {
            swap(x, y);
        }
        updata(1, id[dfn[x]], id[x], k);
        x = fa[dfn[x]];
    }
    if (dep[x] > dep[y])
    {
        swap(x, y);
    }
    updata(1, id[x], id[y], k);
}
long long ask(int x, int y)
{
    long long ans = 0;
    while (dfn[x] != dfn[y])
    {
        if (dep[dfn[x]] < dep[dfn[y]])
        {
            swap(x, y);
        }
        ans = (ans + query(1, id[dfn[x]], id[x])) % p;
        x = fa[dfn[x]];
    }
    if (dep[x] > dep[y])
    {
        swap(x, y);
    }
    ans = (ans + query(1, id[x], id[y])) % p;
    return ans;
}
int main()
{
    cin >> n >> m >> root >> p;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        v[i] %= p;
    }
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    dfs1(root, 0);
    dfs2(root, root);
    maketree(1, 1, n);
    while (m--)
    {
        cin >> op;
        if (op == 1)
        {
            cin >> l >> r >> k;
            change(l, r, k);
        }
        else if (op == 2)
        {
            cin >> l >> r;
            cout << ask(l, r) << "\n";
        }
        else if (op == 3)
        {
            cin >> x >> k;
            updata(1, id[x], id[x] + sz[x] - 1, k);
        }
        else
        {
            cin >> x;
            cout << query(1, id[x], id[x] + sz[x] - 1)<<"\n";
        }
    }
    return 0;
}