重链剖分模板求调教！（码风良好）

EmptyAlien @ 2023-08-20 16:14:13

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

const int MAXN = 1e5+5;

int n, m, r;
unsigned p;

struct Node {
    int l, r;
    unsigned lz, sum;
} tr[MAXN * 4];
unsigned v[MAXN];

vector<int> G[MAXN];
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rnk[MAXN], num;

void lazy(int k, unsigned v) {
    tr[k].lz += v;
    tr[k].lz %= p;
    tr[k].sum += 1LL * v % p * (tr[k].r - tr[k].l + 1) % p;
}

void pushup(int k) {
    tr[k].sum = (tr[k * 2].sum + tr[k * 2 + 1].sum) % p;
}

void pushdown(int k) {
    lazy(k * 2, tr[k].lz);
    lazy(k * 2 + 1, tr[k].lz);
    tr[k].lz = 0;
}

void build(int k, int l, int r) {
    tr[k] = {l, r, 0, v[rnk[l]]};
    if (l == r) return;
    int md = l + r >> 1;
    build(k * 2, l, md);
    build(k * 2 + 1, md + 1, r);
    pushup(k);
}

void update(int k, int l, int r, unsigned v) {
    if (tr[k].l >= l && tr[k].r <= r)
        return lazy(k, v);
    pushdown(k);
    int md = tr[k].l + tr[k].r >> 1;
    int lc = k * 2, rc = lc + 1;
    if (r <= md) update(lc, l, r, v);
    else if (l > md) update(rc, l, r, v);
    else {
        update(lc, l, md, v);
        update(rc, md + 1, r, v);
    }
    pushup(k);
}

unsigned query(int k, int l, int r) {
    if (tr[k].l >= l && tr[k].r <= r)
        return tr[k].sum;
    pushdown(k);
    int md = tr[k].l + tr[k].r >> 1;
    int lc = k * 2, rc = lc + 1;
    unsigned res = 0;
    if (r <= md) res = query(lc, l, r);
    else if (l > md) res = query(rc, l, r);
    else {
        res += query(lc, l, md);
        res += query(rc, md + 1, r);
        res %= p;
    }
    return res;
}

void dfs1(int u) {
    son[u] = -1;
    siz[u] = 1;
    for (int v : G[u]) {
        if (v == fa[u]) continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs1(v);
        siz[u] += siz[v];
        if (son[u] == -1 || siz[v] > siz[son[u]])
            son[u] = v;
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++num;
    rnk[num] = u;
    if (son[u] == -1) return;
    dfs2(son[u], t);
    for (int v : G[u])
        if (v != son[u] && v != fa[u])
            dfs2(v, v);
}

void update_path(int x, int y, unsigned z) {
    int fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] >= dep[fy])
            update(1, dfn[fx], dfn[x], z), x = fa[fx];
        else
            update(1, dfn[fy], dfn[y], z), y = fa[fy];
        fx = top[x];
        fy = top[y];
    }
    update(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z);
}

unsigned query_path(int x, int y) {
    unsigned res = 0;
    int fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] >= dep[fy])
            res += query(1, dfn[fx], dfn[x]), x = fa[fx];
        else
            res += query(1, dfn[fy], dfn[y]), y = fa[fy];
        res %= p;
        fx = top[x];
        fy = top[y]; 
    }
    res += query(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]));
    res %= p;
    return res;
}

void update_tree(int x, int z) {
    update(1, dfn[x], dfn[x] + siz[x] - 1, z);
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> r >> p;

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

    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

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

    for (int i = 1; i <= m; i++) {
        int opt, x, y;
        unsigned z;
        cin >> opt;
        switch (opt) {
            case 1:
                cin >> x >> y >> z;
                update_path(x, y, z);
                break;
            case 2:
                cin >> x >> y;
                cout << query_path(x, y) << endl;
                break;
            case 3:
                cin >> x >> z;
                update_tree(x, z);
                break;
            case 4:
                cin >> x;
                cout << query_tree(x) << endl;
                break;
        }
    }

    return 0;
}

by EmptyAlien @ 2023-08-20 16:41:56

玄关

by _HyperV_ @ 2023-08-20 16:43:28

在调了，等会。

by _HyperV_ @ 2023-08-20 18:19:13

浅改了一下，有什么不懂的可以来问。

强烈建议您阅读 OI Wiki 上的 树链剖分 页面

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

const int MAXN = 1e5+5;

int n, m, r;
int p;

struct Node {
    int l, r;
    int lz, sum;
} tr[MAXN * 4];
int v[MAXN];

vector<int> G[MAXN];
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], val[MAXN], num;

void lazy(int k, int v) {
    if (!v) 
        return;
    tr[k].lz += v;
    tr[k].lz %= p;
    tr[k].sum = (tr[k].sum + 1LL * v % p * (tr[k].r - tr[k].l + 1) % p) % p;
}

void pushup(int k) {
    tr[k].sum = (tr[k * 2].sum + tr[k * 2 + 1].sum) % p;
}

void pushdown(int k) {
    lazy(k * 2, tr[k].lz);
    lazy(k * 2 + 1, tr[k].lz);
    tr[k].lz = 0;
}

void build(int k, int l, int r) {
    tr[k].l = l, tr[k].r = r; 
    if (l == r) {
        tr[k].sum = val[l];
        return;
    }
    int md = l + r >> 1;
    build(k * 2, l, md);
    build(k * 2 + 1, md + 1, r);
    pushup(k);
}

void update(int k, int l, int r, int v) {
    if (tr[k].r < l || r < tr[k].l)
        return;
    if (tr[k].l >= l && tr[k].r <= r)
        return lazy(k, v);
    pushdown(k);
    int lc = k * 2, rc = lc + 1;
    update(lc, l, r, v); update(rc, l, r, v);
    pushup(k);
}

int query(int k, int l, int r) {
    if (tr[k].r < l || r < tr[k].l)
        return 0;
    if (tr[k].l >= l && tr[k].r <= r)
        return tr[k].sum;
    pushdown(k);
    int lc = k * 2, rc = lc + 1;
    return (query(lc, l, r) + query(rc, l, r)) % p;
}

void dfs1(int u,int f) {
    siz[u] = 1, dep[u] = dep[fa[u] = f] + 1;
    for (int v : G[u]) {
        if (v == fa[u]) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]])
            son[u] = v;
    }
}

void dfs2(int u, int t) {
//  cerr << u << " " << t<< '\n';
    top[u] = t;
    dfn[u] = ++num;
    val[num] = v[u];
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int v : G[u])
        if (v != son[u] && v != fa[u])
            dfs2(v, v);
}

void update_path(int x, int y, int z) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        update(1, dfn[top[x]], dfn[x], z);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) 
        swap(x, y);
    update(1, dfn[x], dfn[y], z);
}

int query_path(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        //cerr <<x << " "<<y<<'\n';
        //cerr <<top[x]<<" " << top[y] << '\n';
        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 update_tree(int x, int z) {
    update(1, dfn[x], dfn[x] + siz[x] - 1, z);
}

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> r >> p;

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

    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

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

    for (int i = 1; i <= m; i++) {
    //  cerr << "fuck\n";
        int opt, x, y;
        int z;
        cin >> opt;
        switch (opt) {
            case 1:
                cin >> x >> y >> z;
                update_path(x, y, z);
                break;
            case 2:
                cin >> x >> y;
                cout << query_path(x, y) << endl;
                break;
            case 3:
                cin >> x >> z;
                update_tree(x, z);
                break;
            case 4:
                cin >> x;
                cout << query_tree(x) << endl;
                break;
        }
    }

    return 0;
}

by _HyperV_ @ 2023-08-20 18:19:34

@Lightning_Creeper

by EmptyAlien @ 2023-08-21 08:59:00

我的 update_path 和 query_path 就是照着 \text{OIwiki} 写的。