37pts 求调qwq

wa on 4-10\ 本地跑死循环qwq

#include <iostream>
#include <algorithm>

typedef int ET;
typedef int NT;
typedef long long DT;

struct Edge
{
    ET end, next;
};

struct Node
{
    NT depth, size, father, heavyson;
    NT rank, top;
};

const int MAXN{ 100000 + 5 };
const int MAXM{ 200000 + 5 };
int MOD{};

Edge E[MAXM]{};
ET head[MAXN]{}, count{};

Node V[MAXN]{};
NT dfn[MAXN]{}, dn{};
DT value[MAXN]{}, valOrder[MAXN]{};

void addEdge(NT start, NT end)
{
    E[++count].end = end;
    E[count].next = head[start];
    head[start] = count;
}

void dfs1(NT now, NT depth)
{
    V[now].depth = depth;
    V[now].size = 1;

    for (ET i = head[now], end{}; i; i = E[i].next)
    {
        end = E[i].end;
        if (!V[end].depth)
        {
            V[end].father = now;
            dfs1(end, depth + 1);
            V[now].size += V[end].size;
            if (V[end].size > V[V[now].heavyson].size) V[now].heavyson = end;
        }
    }
}

void dfs2(NT now, NT top)
{
    V[now].top = top;
    V[now].rank = ++dn;
    dfn[dn] = now;
    valOrder[dn] = value[now];

    if (!V[now].heavyson) return;
    dfs2(V[now].heavyson, top);

    for (ET i = head[now], end{}; i; i = E[i].next)
    {
        end = E[i].end;
        if (!V[end].rank) dfs2(end, end);
    }
}

struct SN
{
    DT val, add;
};

SN tree[MAXN * 4]{};
NT n{};

inline NT mid(NT l, NT r) { return (l + r) / 2; }
inline NT len(NT l, NT r) { return (r - l + 1); }
inline NT ls(NT now) { return now * 2; }
inline NT rs(NT now) { return now * 2 + 1; }

void make_add(NT now, DT val, NT len)
{
    tree[now].val = (tree[now].val + len * val) % MOD;
    tree[now].add = (tree[now].add + val) % MOD;
}

void push_up(NT now)
{
    tree[now].val = (tree[ls(now)].val + tree[rs(now)].val) % MOD;
    //using std::cout;
    //using std::endl;
    //cout << "-----" << endl;
    //cout << now << " " << ls(now) << " " << rs(now) << endl;
    //cout << tree[now].val << " " << tree[ls(now)].val << " " << tree[rs(now)].val << endl;
}

void push_down(NT now, NT len)
{
    if (len <= 1) return;

    make_add(ls(now), tree[now].add, len - len / 2);
    make_add(rs(now), tree[now].add, len / 2);

    tree[now].add = 0;
}

// void build(NT l = 1, NT r = size)
// {
//  NT log{};
//  for(log = 1; log < r; log <<= 1);

//  for (NT i{log}; i < log + r; i++) tree[i].val = value[i - log];
//  for (NT i{log - 1}; i >= 0; i--) push_up(i);
// }

void build(NT now = 1, NT l = 1, NT r = n)
{
    if (l == r)
    {
        tree[now].val = (valOrder[l] % MOD);
        return;
    }
    NT m{mid(l, r)};
    build(ls(now), l, m);
    build(rs(now), m + 1, r);
    push_up(now);
}

void update(NT l, NT r, DT val, NT now = 1, NT cl = 1, NT cr = n)
{
    if (l <= cl && cr <= r)
    {
        make_add(now, val, len(cl, cr));
        return;
    }
    push_down(now, len(cl, cr));
    NT m{ mid(cl, cr) };
    if (l <= m) update(l, r, val, ls(now), cl, m);
    if (m < r) update(l, r, val, rs(now), m + 1, cr);
    push_up(now);
}

DT query(NT l, NT r, NT now = 1, NT cl = 1, NT cr = n)
{
    if (l <= cl && cr <= r) return tree[now].val;
    push_down(now, len(cl, cr));
    NT m{ mid(cl, cr) };
    DT ans{};
    if (l <= m) ans += query(l, r, ls(now), cl, m);
    if (m < r) ans += query(l, r, rs(now), m + 1, cr);
    return ans;
}

DT qRange(NT x, NT y)
{
    DT ans{};
    while (V[x].top != V[y].top)
    {
        if (V[V[x].top].depth < V[V[y].top].depth) std::swap(x, y);
        ans = (ans + query(V[V[x].top].rank, V[x].rank)) % MOD;
        x = V[V[x].top].father;
    }
    if (V[x].depth > V[y].depth) std::swap(x, y);
    ans += query(V[x].rank, V[y].rank);
    return ans;
}

void updRange(NT x, NT y, DT val)
{
    val %= MOD;
    while (V[x].top != V[y].top)
    {
        if (V[V[x].top].depth < V[V[y].top].depth) std::swap(x, y);
        update(V[V[x].top].rank, V[x].rank, val);
        x = V[V[x].top].father;
    }
    if (V[x].depth > V[y].depth) std::swap(x, y);
    update(V[x].rank, V[y].rank, val);
}

DT qSon(NT now)
{
    return query(V[now].rank, V[now].rank + V[now].size - 1);
}

void updSon(NT now, DT val)
{
    update(V[now].rank, V[now].rank + V[now].size - 1, val);
}

int main()
{
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int m{}, r{};
    int k{}, x{}, y{}, z{};
    cin >> n >> m >> r >> MOD;
    for (NT i = 1; i <= n; i++) cin >> value[i];
    for (ET i = 0, x{}, y{}; i < n - 1; i++)
    {
        cin >> x >> y;
        addEdge(x, y);
        addEdge(y, x);
    }
    dfs1(r, 1);
    dfs2(r, r);
    build();
    while (m--)
    {
        cin >> k;
        switch (k)
        {
        case 1:
            cin >> x >> y >> z;
            updRange(x, y, z);
            break;
        case 2:
            cin >> x >> y;
            cout << qRange(x, y) << endl;
            break;
        case 3:
            cin >> x >> y;
            updSon(x, y);
            break;
        case 4:
            cin >> x;
            cout << qSon(x) << endl;
            break;
        default:
            break;
        }
    }
}