10pts 求调 只过 #11

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150#include <conio.h>
#include <stdio.h>
#include <vector>

class Node
{
public:
    int dta, dfn, end, dep = 0, siz = 1;
    Node *top, *fa = nullptr, *son = nullptr;
    std::vector<Node *> to;
} *node[100001], *rnk[100001];

int ans, i, j, m, n, p, r, res, t, tmr, x, y, z;
long long d[100001], mul[100001];

void dfs1(Node *const now)
{
    for (Node *next : now->to)
        if (next != now->fa)
        {
            next->fa = now;
            next->dep = now->dep + 1;
            dfs1(next);
            now->siz += next->siz;
            if (!now->son || now->son->siz < next->siz)
                now->son = next;
        }
}

void dfs2(Node *const now)
{
    now->dfn = ++tmr;
    rnk[now->dfn] = now;
    if (now->son)
    {
        now->son->top = now->top;
        dfs2(now->son);
        for (Node *next : now->to)
            if (next != now->fa && next != now->son)
            {
                next->top = next;
                dfs2(next);
            }
    }
    now->end = tmr;
}

void add(int left, int right, const int val)
{
    if (left > right)
        std::swap(left, right);
    for (i = left; i <= n; i += i & -i)
    {
        d[i] += val;
        mul[i] += (long long)val * left;
    }
    for (i = right + 1; i <= n; i += i & -i)
    {
        d[i] -= val;
        mul[i] -= (long long)val * (right + 1);
    }
}

const int get(int left, int right)
{
    res = 0;
    if (left > right)
        std::swap(left, right);
    for (i = left - 1; i; i -= i & -i)
        res = (res - (d[i] * left - mul[i]) % p + p) % p;
    for (i = right; i; i -= i & -i)
        res = (res + d[i] * (right + 1) - mul[i]) % p;
    return res;
}

void pa(Node *u, Node *v, const int val)
{
    while (u->top != v->top)
    {
        if (u->top->dep < v->top->dep)
            std::swap(u, v);
        add(u->dfn, u->top->dfn, val);
        u = u->top->fa;
    }
    add(u->dfn, v->dfn, val);
}

const int pq(Node *u, Node *v)
{
    ans = 0;
    while (u->top != v->top)
    {
        if (u->top->dep < v->top->dep)
            std::swap(u, v);
        ans = (ans + get(u->dfn, u->top->dfn)) % p;
        u = u->top->fa;
    }
    ans = (ans + get(u->dfn, v->dfn)) % p;
    return ans;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &r, &p);
    for (i = 1; i <= n; ++i)
    {
        node[i] = new Node;
        scanf("%d", &node[i]->dta);
    }
    for (i = 1; i < n; ++i)
    {
        scanf("%d%d", &x, &y);
        node[x]->to.push_back(node[y]);
        node[y]->to.push_back(node[x]);
    }
    node[r]->top = node[r];
    dfs1(node[r]);
    dfs2(node[r]);
    for (i = 1; i <= n; ++i)
        d[node[i]->dfn] = node[i]->dta;
    for (i = n; i > 1; --i)
    {
        d[i] -= d[i - 1];
        mul[i] = d[i] * i;
    }
    mul[1] = d[1];
    for (i = 1; i <= n; ++i)
        for (j = (i & -i) >> 1; j; --j)
        {
            d[i] += d[i - j];
            mul[i] += mul[i - j];
        }
    while (m--)
    {
        scanf("%d%d", &t, &x);
        if (t == 1)
        {
            scanf("%d%d", &y, &z);
            pa(node[x], node[y], z);
        }
        else if (t == 2)
        {
            scanf("%d", &y);
            printf("%d\n", pq(node[x], node[y]));
        }
        else if (t == 3)
        {
            scanf("%d", &z);
            add(node[x]->dfn, node[x]->end, z);
        }
        else
            printf("%d\n", get(node[x]->dfn, node[x]->end));
    }

    getch();
    return 0;
}