Author: lllyouo
Date: 20251014
tag: 树上问题, 树链剖分
link: https://www.luogu.com.cn/problem/P3384

问题描述

link

分析

略

参考代码

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

const int N = 1e5 + 10;

struct SegmentTree {
    int l, r, dat;
    int lazy; // 懒惰标记
} t[N * 4];

int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], dfn_cnt, rnk[N];
int h[N], e[2 * N], ne[2 * N], idx;
int n, m, r, p, a[N];

void add(int x, int y) {
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

void pushup(int p) {
    t[p].dat = t[p << 1].dat + t[p << 1 | 1].dat;
}

void pushdown(int p) {
    if (t[p].lazy) {
        t[p << 1].dat += t[p].lazy * (t[p << 1].r - t[p << 1].l + 1);
        t[p << 1 | 1].dat += t[p].lazy * (t[p << 1 | 1].r - t[p << 1 | 1].l + 1);
        t[p << 1].lazy += t[p].lazy;
        t[p << 1 | 1].lazy += t[p].lazy;
        t[p].lazy = 0;
    }
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        t[p].dat = rnk[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

void modify(int p, int l, int r, int v) {
    if (t[p].l >= l && t[p].r <= r) {
        t[p].dat += v * (t[p].r - t[p].l + 1);
        t[p].lazy += v;
        return;
    }

    pushdown(p);

    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) modify(p << 1, l, r, v);
    if (r > mid) modify(p << 1 | 1, l, r, v);

    pushup(p);
}

int query(int p, int l, int r) {
    if (t[p].l >= l && t[p].r <= r) return t[p].dat;

    pushdown(p);

    int mid = (t[p].l + t[p].r) >> 1;
    int ans = 0;
    if (l <= mid) ans += query(p << 1, l, r);
    if (r > mid) ans += query(p << 1 | 1, l, r);
    return ans;
}

void dfs1(int u, int f) {
    fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int ftop) {
    top[u] = ftop, dfn[u] = ++dfn_cnt, rnk[dfn_cnt] = a[u];

    if (son[u]) dfs2(son[u], ftop); // 存在重儿子则深入

    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (v != son[u] && v != fa[u]) dfs2(v, v); // 存在轻儿子则深入
    }
}

void modify_path(int x, int y, int v) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        modify(1, dfn[top[x]], dfn[x], v);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    modify(1, dfn[y], dfn[x], v);
}

void modify_tree(int x, int v) {
    modify(1, dfn[x], dfn[x] + siz[x] - 1, v);
}

int query_path(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += query(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    ans += query(1, dfn[y], dfn[x]);
    return ans;
}

int query_tree(int x) {
    return query(1, dfn[x], dfn[x] + siz[x] - 1);
}

signed main() {
    cin >> n >> m >> r >> p;
    for (int i = 1; i <= n; i++) cin >> a[i];

    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y), add(y, x);
    }

    dfs1(r, 0);
    dfs2(r, r);
    build(1, 1, n);

    while (m--) {
        int o, x, y, z;
        cin >> o >> x;
        if (o == 1) {
            cin >> y >> z;
            modify_path(x, y, z);
        } else if (o == 2) {
            cin >> y;
            cout << query_path(x, y) % p << endl;
        } else if (o == 3) {
            cin >> z;
            modify_tree(x, z);
        } else {
            cout << query_tree(x) % p << endl;
        }
    }

    return 0;
}