求调（样例过不了

心血来潮打一份树剖板题，然后热血的心就凉透了。

信息：1.线段树只删去 mod 单独交板题是 AC 的。

2.树链剖分只删去 mod 单独交 LCA 是 AC 的。

3.树链剖分的数组数值和题解 1 非常不一样。。。

4.将树链剖分的数组数值全部改为题解 1 后，答案仍然不正确。

求巨佬调！！！

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void read(T &x)
{
    x = 0;
    register char c = getchar();
    register short f = 1;
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    x *= f;
}

template <typename T, typename... Args>
inline void read(T &x, Args &...temps)
{
    read(x), read(temps...);
}

const int N = 1e5 + 5;
typedef long long ll;
int n, m, root, mod, w[N];
vector<int> g[N];

int fa[N], siz[N], dep[N], son[N];
void dfs1(int x)
{
    siz[x] = 1;
    for (auto y : g[x])
    {
        if (y == fa[x])
            continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs1(y);
        siz[x] += siz[y];
        if (siz[son[x]] < siz[y])
            son[x] = y;
    }
}

int top[N], id[N], tot, v[N];
void dfs2(int x, int Top)
{
    id[x] = ++tot;
    v[tot] = w[x];
    top[x] = Top;
    if (son[x])
        dfs2(son[x], Top);
    for (auto y : g[x])
    {
        if (y == fa[x] || y == son[x])
            continue;
        dfs2(y, y);
    }
}

class Segment_Tree
{
private:
    int l[N << 2], r[N << 2];
    ll val[N << 2], tag[N << 2];

public:
    Segment_Tree() {}
#define lt (p << 1)
#define rt (p << 1 | 1)
    void push_up(int p)
    {
        val[p] = (val[lt] + val[rt]) % mod;
    }
    void build(int p, int L, int R)
    {
        l[p] = L;
        r[p] = R;
        if (L == R)
            return (void)(val[p] = v[L] % mod);
        int mid = L + R >> 1;
        build(lt, L, mid);
        build(rt, mid + 1, R);
        push_up(p);
    }
    void push_down(int p)
    {
        if (tag[p])
        {
            (val[lt] += tag[p] * (r[lt] - l[lt] + 1)) %= mod;
            (val[rt] += tag[p] * (r[rt] - l[rt] + 1)) %= mod;
            (tag[lt] += tag[p]) %= mod;
            (tag[rt] += tag[p]) %= mod;
            tag[p] = 0;
        }
    }
    void modify(int p, int L, int R, ll k)
    {
        if (l[p] >= L && r[p] <= R)
        {
            (val[p] += k * (r[p] - l[p] + 1)) %= mod;
            (tag[p] += k) %= mod;
            return;
        }
        push_down(p);
        int mid = l[p] + r[p] >> 1;
        if (L <= mid)
            modify(lt, L, R, k);
        if (R > mid)
            modify(rt, L, R, k);
        push_up(p);
    }
    ll query(int p, int L, int R)
    {
        if (l[p] >= L && r[p] <= R)
            return val[p];
        push_down(p);
        int mid = l[p] + r[p] >> 1;
        ll ret = 0;
        if (L <= mid)
            ret = query(lt, L, R);
        if (R > mid)
            ret += query(rt, L, R);
        return ret % mod;
    }
#undef lt
#undef rt
} seg;

void modify1(int x, int y, ll z)
{
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            x ^= y ^= x ^= y;
        seg.modify(1, id[top[x]], id[x], z);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        x ^= y ^= x ^= y;
    seg.modify(1, id[x], id[y], z);
}

ll query2(int x, int y)
{
    ll ret = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            x ^= y ^= x ^= y;
        (ret += seg.query(1, id[top[x]], id[x])) %= mod;
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        x ^= y ^= x ^= y;
    (ret += seg.query(1, id[x], id[y])) %= mod;
    return ret;
}

void modify3(int x, int z)
{
    seg.modify(1, id[x], id[x] + siz[x] - 1, z);
}

ll query4(int x)
{
    return seg.query(1, id[x], id[x] + siz[x] - 1);
}

signed main()
{
    read(n, m, root, mod);
    for (int i = 1; i <= n; i++)
        read(w[i]);
    for (int i = 1, x, y; i < n; i++)
    {
        read(x, y);
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    dfs1(root);
    dfs2(root, root);
    seg.build(1, 1, n);
    for (int op, x, y, z; m--;)
    {
        read(op);
        if (op == 1)
        {
            read(x, y, z);
            modify1(x, y, z);
        }
        else if (op == 2)
        {
            read(x, y);
            printf("%lld\n", query2(x, y));
        }
        else if (op == 3)
        {
            read(x, z);
            modify3(x, y);
        }
        else
        {
            read(x);
            printf("%lld\n", query4(x));
        }
    }

    return 0;
}