树链剖分

先把我调了一晚上的代码贴上，明天再写博客吧

#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

typedef long long ll;
const int N = 2e5 + 10;

ll sum[N << 2], lazy[N << 2];
int head[N], value[N], nex[N << 1], to[N << 1], cnt;
int fa[N], sz[N], dep[N], id[N], rk[N], son[N], top[N], tot;
int n, m, mod;

void dfs1(int rt, int f) {
    dep[rt] = dep[f] + 1;
    sz[rt] = 1; fa[rt] = f;
    for(int i = head[rt]; ~i; i = nex[i]) {
        if(to[i] == f)  continue;
        dfs1(to[i], rt);
        sz[rt] += sz[to[i]];
        if(!son[rt] || sz[to[i]] > sz[son[rt]])
            son[rt] = to[i];
    }
}

void dfs2(int rt, int t) {
    top[rt] = t;
    id[rt] = ++tot;
    rk[tot] = rt;
    if(!son[rt])
        return ;
    dfs2(son[rt], t);
    for(int i = head[rt]; ~i; i = nex[i]) {
        if(to[i] == fa[rt] || to[i] == son[rt]) continue;
        dfs2(to[i], to[i]);
    }
}

void updown(int rt, int l, int r) {
    if(lazy[rt]) {
        sum[ls] = (sum[ls] + (mid - l + 1) * lazy[rt] % mod) % mod;
        sum[rs] = (sum[rs] + (r - mid) * lazy[rt] % mod) % mod;
        lazy[ls] = (lazy[ls] + lazy[rt]) % mod;
        lazy[rs] = (lazy[rs] + lazy[rt]) % mod;
        lazy[rt] = 0;
    }
}

void build(int rt, int l, int r) {
    if(l == r) {
        sum[rt] = value[rk[l]];
        return ;
    }
    build(lson);
    build(rson);
    sum[rt] = (sum[ls] + sum[rs]) % mod;
}

ll query(int rt, int l, int r, int L, int R) {
    if(l >= L && r <= R)    return sum[rt];
    updown(rt, l, r);
    ll ans = 0;
    if(L <= mid)    ans += query(lson, L, R);
    if(R > mid)     ans += query(rson, L, R);
    return ans;
}

void update(int rt, int l, int r, int L, int R, int k) {
    if(l >= L && r <= R) {
        sum[rt] = (sum[rt] + (r - l + 1) * k % mod) % mod;
        lazy[rt] = (lazy[rt] + k) % mod;
        return ;
    }
    updown(rt, l, r);
    if(L <= mid)    update(lson, L, R, k);
    if(R > mid)     update(rson, L, R, k);
    sum[rt] = (sum[ls] + sum[rs]) % mod;
}

void print(int rt, int l, int r) {
    if(l == r) {
        printf("%lld\n", sum[rt]);
        return ;
    }
    updown(rt, l, r);
    print(lson);
    print(rson);
}

void op1(int x, int y, int k) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]])   swap(x, y);
        update(1, 1, n, id[top[x]], id[x], k);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    update(1, 1, n, id[x], id[y], k);
}

ll op2(int x, int y) {
    ll ans = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]])   swap(x, y);
        ans = (ans + query(1, 1, n, id[top[x]], id[x])) % mod;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    ans = (ans + query(1, 1, n, id[x], id[y])) % mod;
    return ans % mod;
}

void op3(int x, int k) {
    update(1, 1, n, id[x], id[x] + sz[x] - 1, k);
}

ll op4(int x) {
    return query(1, 1, n, id[x], id[x] + sz[x] - 1);
}

void add(int x, int y) {
    to[cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt++;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    memset(head, -1, sizeof head), cnt = 0;
    int x, y, rt, op, z;
    scanf("%d %d %d %d", &n, &m, &rt, &mod);
    for(int i = 1; i <= n; i++)
        scanf("%d", &value[i]);
    for(int i = 1; i < n; i++) {
        scanf("%d %d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs1(rt, 0);
    dfs2(rt, rt);
    // int fa[N], son[N], sz[N], id[N], rk[N], tp[N], dep[N], tot;
    // for(int i = 1; i <= n; i++)
    //     printf("%d %d %d %d %d %d\n", fa[i], son[i], sz[i], id[i], top[i], dep[i]);
    build(1, 1, n);
    // print(1, 1, n);
    // puts("");
    for(int i = 0; i < m; i++) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d %d %d", &x, &y, &z);
            op1(x, y, z);
        }
        else if(op == 2) {
            scanf("%d %d", &x, &y);
            printf("%lld\n", op2(x, y) % mod);
        }
        else if(op == 3) {
            scanf("%d %d", &x, &y);
            op3(x, y);
        }
        else {
            scanf("%d", &x);
            printf("%lld\n", op4(x) % mod);
        }
    }
    // print(1, 1, n);
    return 0;
}

树链剖分

原文：https://www.cnblogs.com/lifehappy/p/12944963.html