树剖模板题WA求调

rt, qwq

#include <cstdio>
#include <vector>

using namespace std;

constexpr int N = 1e5 + 10;

int n, m, r, p, cnt, a_[N], a[N], fa[N], top[N], id[N], sze[N], son[N], dep[N], tr[N << 2], tag[N << 2];
vector <int> g[N];

inline void dfs_1 (int u, int fa_, int dep_)
{
    dep[u] = dep_, fa[u] = fa_, sze[u] = 1;
    for (auto &v : g[u])
        if (v != fa_)
        {
            dfs_1 (v, u, dep_ + 1);
            sze[u] += sze[v], son[u] = (!son[u] ? v : (sze[son[u]] >= sze[v] ? son[u] : v));
        }
}

inline void dfs_2 (int u, int top_)
{
    id[u] = ++cnt, a[cnt] = a_[u], top[u] = top_;
    if (!son[u]) return ;
    dfs_2 (son[u], top_);
    for (auto &v : g[u])
        if (v != fa[u] && v != son[u]) dfs_2 (v, v);
}

inline void build (int x = 1, int l = 1, int r = n)
{
    if (l == r) tr[x] = a[l] % p;
    else
    {
        int mid = l + r >> 1;
        build (x << 1, l, mid), build (x << 1 | 1, mid + 1, r);
        tr[x] = (tr[x << 1] + tr[x << 1 | 1]) % p;
    }
}

inline void push_down (int x, int l, int r, int mid)
{
    tr[x << 1] += tag[x] * (mid - l + 1), tr[x << 1 | 1] += tag[x] * (r - mid);
    tr[x << 1] %= p, tr[x << 1 | 1] %= p;
    tag[x << 1] += tag[x], tag[x << 1 | 1] += tag[x], tag[x] = 0;
}

inline void update (int l, int r, int d, int x = 1, int nl = 1, int nr = n)
{
    if (nl > r || nr < l) return ;
    if (nl <= l && nr >= r) tr[x] += d * (nr - nl + 1), tag[x] += d;
    else
    {
        int mid = nl + nr >> 1;
        push_down (x, nl, nr, mid);
        update (l, r, d, x << 1, nl, mid), update (l, r, d, x << 1 | 1, mid + 1, nr);
        tr[x] = (tr[x << 1] + tr[x << 1 | 1]) % p;
    }
}

inline int query (int l, int r, int x = 1, int nl = 1, int nr = n)
{
    if (nl > r || nr < l) return 0;
    if (nl <= l && nr >= r) return tr[x] % p;
    else
    {
        int mid = nl + nr >> 1;
        push_down (x, nl, nr, mid);
        return (query (l, r, x << 1, nl, mid) + query (l, r, x << 1 | 1, mid + 1, nr)) % p;
    }
}

inline void update_range (int x, int y, int d)
{
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) x ^= y ^= x ^= y;
        update (id[top[x]], id[x], d), x = fa[top[x]];
    }
    if (dep[x] > dep[y]) x ^= y ^= x ^= y;
    update (id[x], id[y], d);
}

inline void update_son (int x, int d)
{
    update (id[x], id[x] + sze[x] - 1, d);
}

inline int query_range (int x, int y)
{
    int res = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) x ^= y ^= x ^= y;
        res = (res + query (id[top[x]], id[x])) % p, x = fa[top[x]];
    }
    if (dep[x] > dep[y]) x ^= y ^= x ^= y;
    res = (res + query (id[x], id[y])) % p;
    return res;
}

inline int query_son (int x)
{
    return query (id[x], id[x] + sze[x] - 1);
}

namespace FAST_IO_II
{
    inline void write (char ch) { putchar (ch); }
    inline void write (char s[]) { while (*s) putchar (*s++); }
    template <class T> inline void read (T &x) { x = 0; int sgn = false; char c = getchar (); while (c < '0' || c > '9') sgn |= c == '-', c = getchar (); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar (); x = sgn ? ~x + 1 : x; }
    template <class T> inline void write (T x) { static char c[20]; unsigned p = 0; if (x < 0) putchar ('-'), x = ~x + 1; do c[++p] = x % 10 ^ 48, x /= 10; while (x); while (p) putchar (c[p]), --p; }
    template <class T, class... U> inline void read (T &x, U &...t) { read (x), read (t...); }
    template <class T, class... U> inline void write (T x, U ...t) { write (x), write (t...); }
};
using namespace FAST_IO_II;

int main ()
{
    read (n, m, r, p);
    for (int i = 1; i <= n; ++i) read (a_[i]);
    for (int i = 1, u, v; i < n; ++i) read (u, v), g[u].push_back (v), g[v].push_back (u);
    dfs_1 (r, 0, 1), dfs_2 (r, r), build ();
    while (m--)
    {
        int opt, x, y, z;
        read (opt);
        if (opt == 1) read (x, y, z), update_range (x, y, z % p);
        if (opt == 2) read (x, y), write (query_range (x, y), '\n');
        if (opt == 3) read (x, y), update_son (x, y % p);
        if (opt == 4) read (x), write (query_son (x), '\n');
    }
    return 0;
}