\Large{心理}战术的重要性

既然进来了，给我调一下吧

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5;

int n, m, root;
long long P;

long long w[N + 5];
vector<int> g[N + 5];

namespace SGT // Ï߶ÎÊ÷²¿·Ö
{
    struct SegmentTree
    {
    private:
        struct Node
        {
            long long sum;
            int l, r;
        } tree[N * 4 + 5];
        long long tag[N * 4 + 5];

        Node merge(Node lnode, Node rnode)
        {
            Node res{};
            res.sum = (lnode.sum + rnode.sum) % P;
            res.l = lnode.l;
            res.r = rnode.r;
            return res;
        }

        inline int lc(int p)
        {
            return p << 1;
        }

        inline int rc(int p)
        {
            return p << 1 | 1;
        }

        inline void push_up(int p)
        {
            tree[p] = merge(tree[lc(p)], tree[rc(p)]);
        }

        inline void push_down(int p)
        {
            if (tag[p])
            {
                tag[lc(p)] = (tag[lc(p)] + tag[p]) % P;
                tag[rc(p)] = (tag[rc(p)] + tag[p]) % P;
                tree[lc(p)].sum = (tree[lc(p)].sum + tag[p] * (tree[lc(p)].r - tree[lc(p)].l + 1) % P) % P;
                tree[rc(p)].sum = (tree[rc(p)].sum + tag[p] * (tree[rc(p)].r - tree[rc(p)].l + 1) % P) % P;
                tag[p] = 0;
            }
        }

        void build(int p, int bl, int br, int *idx, long long *a)
        {
            tree[p].l = bl;
            tree[p].r = br;
            tag[p] = 0;

            if (bl == br)
            {
                tree[p].sum = a[idx[bl]] % P;
                return;
            }

            int mid = bl + br >> 1;
            build(lc(p), bl, mid, idx, a);
            build(rc(p), mid + 1, br, idx, a);
            push_up(p);
        }

        void update(int p, int ul, int ur, long long x)
        {
            if (ul <= tree[p].l && tree[p].r <= ur)
            {
                tree[p].sum += x * (tree[p].r - tree[p].l + 1) % P;
                tag[p] = (tag[p] + x % P) % P;
                return;
            }

            push_down(p);
            int mid = tree[p].l + tree[p].r >> 1;
            if (ur <= mid) update(lc(p), ul, ur, x);
            else if (ul > mid) update(rc(p), ul, ur, x);
            else update(lc(p), ul, ur, x), update(rc(p), ul, ur, x);
            push_up(p);
        }

        long long query(int p, int ql, int qr)
        {
            if (ql <= tree[p].l && tree[p].r <= qr)
                return tree[p].sum;
            push_down(p);
            int mid = tree[p].l + tree[p].r >> 1;
            if (qr <= mid) return query(lc(p), ql, qr);
            else if (ql > mid) return query(rc(p), ql, qr);
            else return (query(lc(p), ql, qr) + query(rc(p), ql, qr)) % P;
        }

    public:
        void build(int n, int *idx, long long *a)
        {
            build(1, 1, n, idx, a);
        }

        void update(int ul, int ur, long long x)
        {
            update(1, ul, ur, x);
        }

        long long query(int ql, int qr)
        {
            return query(1, ql, qr);
        }
    } segt;
}

namespace HPD // Ê÷Á´ÆÊ·Ö
{
    int fa[N + 5];   // ¸¸½Úµã.
    int sz[N + 5];   // ×ÓÊ÷´óС.
    int top[N + 5];  // ËùÔÚÖØÁ´µÄ¶¥¶Ë.
    int hson[N + 5]; // ÖØ×Ó½Úµã.
    int dfn[N + 5];  // DFS Ðò.
    int seq[N + 5];  // DFS ÐòÖÐµÚ i ¸ö½Úµã.
    int deep[N + 5]; // Éî¶È.
    int dfn_tot;

    int dfs1(int u)
    {
        sz[u] = 1;
        hson[u] = 0;

        for (auto v : g[u])
        {
            if (v != fa[u])
            {
                fa[v] = u;
                deep[v] = deep[u] + 1;
                sz[u] += dfs1(v);
                if (sz[v] > sz[hson[u]]) hson[u] = v;
            }
        }

        return sz[u];
    }

    void dfs2(int u)
    {
        seq[++dfn_tot] = u;
        dfn[u] = dfn_tot;

        if (hson[u] != 0)
        {
            top[hson[u]] = top[u];
            dfs2(hson[u]);
        }

        for (auto v : g[u])
        {
            if (v != fa[u] && v != hson[u])
            {
                top[v] = v;
                dfs2(v);
            }
        }
    }
}

namespace SOLVE // ÐÞ¸Ä/²éѯ ²¿·Ö
{
    void update_pass(int u, int v, long long x)
    {
        while (HPD::top[u] != HPD::top[v])
        {
            if (HPD::deep[u] < HPD::deep[v]) swap(u, v);
            SGT::segt.update(HPD::dfn[u], HPD::dfn[HPD::top[u]], x);
            u = HPD::fa[HPD::top[u]];
        }

        if (HPD::deep[u] > HPD::deep[v]) swap(u, v);
        SGT::segt.update(HPD::dfn[u], HPD::dfn[v], x);
    }

    long long query_pass(int u, int v)
    {
        long long res = 0;

        while (HPD::top[u] != HPD::top[v])
        {
            if (HPD::deep[u] < HPD::deep[v]) swap(u, v);
            res = (res + SGT::segt.query(HPD::dfn[u], HPD::dfn[HPD::top[u]])) % P;
            u = HPD::fa[HPD::top[u]];
        }

        if (HPD::deep[u] > HPD::deep[v]) swap(u, v);
        res = (res + SGT::segt.query(HPD::dfn[u], HPD::dfn[v])) % P;

        return res;
    }

    void update_subtree(int u, long long x)
    {
        SGT::segt.update(HPD::dfn[u], HPD::dfn[u] + HPD::sz[u] - 1, x);
    }

    long long query_subtree(int u)
    {
        return SGT::segt.query(HPD::dfn[u], HPD::dfn[u] + HPD::sz[u] - 1);
    }
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m >> root >> P;

    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i];
        w[i] %= P;
    }

    for (int i = 1; i <= n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    HPD::fa[root] = 0;
    HPD::deep[root] = 1;
    HPD::dfs1(root);

    HPD::top[root] = root;
    HPD::dfs2(root);

    SGT::segt.build(n, HPD::seq, w);

    while (m--)
    {
        int op;
        cin >> op;

        if (op == 1)
        {
            int x, y;
            long long z;
            cin >> x >> y >> z;
            SOLVE::update_pass(x, y, z);
        }
        else if (op == 2)
        {
            int x, y;
            cin >> x >> y;
            cout << SOLVE::query_pass(x, y) << endl;
        }
        else if (op == 3)
        {
            int x;
            long long z;
            cin >> x >> z;
            SOLVE::update_subtree(x, z);
        }
        else
        {
            int x;
            cin >> x;
            cout << SOLVE::query_subtree(x) << endl;
        }
    }

    return 0;
}