树链剖分

原理

重链上结点的编号是连续的。

模板题

洛谷-P3384-【模板】轻重链剖分

#include <iostream>
#include <cstring>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;

typedef long long LL;
const int N = 100010;
struct edge {
    int to, next;
};
edge e[2 * N];
int idx, head[N];
int n, m, r, p;
int temp[N], w[N];
int dep[N], fa[N], size[N];
int heavy_son[N], top[N];
int cnt, dfn[N];
struct node {
    int l, r;
    int data;
    int add;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define data(x) t[x].data
    #define add(x) t[x].add
};
node t[N << 2];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs1 (int cur, int father) {
    size[cur] = 1;
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (to == father) continue;
        dep[to] = dep[cur] + 1;
        fa[to] = cur;
        dfs1(to, cur);
        size[cur] += size[to];
        if (size[to] > size[heavy_son[cur]])
            heavy_son[cur] = to;
    }
}
void dfs2 (int cur, int top_node) {
    dfn[cur] = ++ cnt;
    w[dfn[cur]] = temp[cur];
    top[cur] = top_node;
    if (heavy_son[cur]) dfs2(heavy_son[cur], top_node);
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (to == fa[cur] || to == heavy_son[cur]) continue;
        dfs2(to, to);
    }
}
void update (int rt) {
    data(rt) = (data(ls) + data(rs)) % p;
}
void build (int rt, int l, int r) {
    l(rt) = l, r(rt) = r;
    if (l == r) {
        data(rt) = w[l] % p;
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    update(rt);
}
void spread (int rt) {
    if (add(rt)) {
        data(ls) = (data(ls) + (LL)add(rt) * (r(ls) - l(ls) + 1)) % p;
        data(rs) = (data(rs) + (LL)add(rt) * (r(rs) - l(rs) + 1)) % p;

        add(ls) = (add(ls) + add(rt)) % p;
        add(rs) = (add(rs) + add(rt)) % p;

        add(rt) = 0;
    }
}
void modify (int rt, int l, int r, int val) {
    if (l <= l(rt) && r(rt) <= r) {
        data(rt) = (data(rt) + (LL)val * (r(rt) - l(rt) + 1)) % p;
        add(rt) = (add(rt) + val) % p;
        return;
    }
    spread(rt);
    int mid = l(rt) + r(rt) >> 1;
    if (l <= mid) modify(ls, l, r, val);
    if (r >= mid + 1) modify(rs, l, r, val);
    update(rt);
}
int query (int rt, int l, int r) {
    if (l <= l(rt) && r(rt) <= r) return data(rt);
    spread(rt);
    int mid = l(rt) + r(rt) >> 1;
    int res = 0;
    if (l <= mid) res = (res + query(ls, l, r)) % p;
    if (r >= mid + 1) res = (res + query(rs, l, r)) % p;
    return res;
}
void modify_path (int x, int y, int val) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        modify(1, dfn[top[x]], dfn[x], val);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    modify(1, dfn[x], dfn[y], val);
}
int query_path (int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res = (res + query(1, dfn[top[x]], dfn[x])) % p;
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    res = (res + query(1, dfn[x], dfn[y])) % p;
    return res;
}
void modify_subtree (int x, int val) {
    modify(1, dfn[x], dfn[x] + size[x] - 1, val);
}
int query_subtree (int x) {
    return query(1, dfn[x], dfn[x] + size[x] - 1);
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &r, &p);
    for (int i = 1; i <= n; ++ i) scanf("%d", &temp[i]);
    for (int i = 1, u, v; i <= n - 1; ++ i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }

    dfs1(r, -1);
    dfs2(r, r);
    build(1, 1, n);
    while (m --) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            modify_path(x, y, z);
        } else if (opt == 2) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", query_path(x, y));
        } else if (opt == 3) {
            int x, y;
            scanf("%d%d", &x, &y);
            modify_subtree(x, y);
        } else {
            int x;
            scanf("%d", &x);
            printf("%d\n", query_subtree(x));
        }
    }
    return 0;
}