重链剖分

重链剖分是一种以 \(O(\log^2 n)\) 时间复杂度维护树上路径，同时支持 dfs 序相关操作的算法。

基本定义

• 子树大小 sz[u]：以 \(u\) 为根的子树中所含节点的数量；
• 重儿子 son[u]：节点 \(u\) 的所有儿子 \(v\) 中，sz[v]最大的一个；
• 重边：由一个非叶子节点指向其重儿子的边；
• 重链：由若干重边组成的连续的链；

算法原理

如果我们设定 dfs 的遍历顺序，使对于任意一个非叶子节点 \(u\)，它的重儿子 son[u] 总是在所有儿子中最先被访问到。这样，一条重链上所有节点的 dfs 序一定是连续的。

我们可以使用线段树维护重链，并将待查询路径分解为若干条重链组成，在分解得到的每一条重链上进行区修区查，再合并所有结果，就能实现路径修改、路径查询。

时间复杂度证明

我们发现，从一个节点 \(u\) 转移到它的一个轻儿子 \(v\) 上， sz[v] 至少减小为 sz[u] 的 \(\frac{1}{2}\)。

因此任意一条自上而下的路径中所包含的重链条数一定不超 \(\log n\) 条（因为连接两条相邻重链的边一定是轻边）。

对每一条重链，线段树的区修区查复杂度的上界是 \(O(\log n)\)。因此单次修改的总时间复杂度上界为 \(O(\log^2 n)\)。

例题

P3384 【模板】重链剖分/树链剖分

该题目中还用一个操作：子树修改子树查询。

我们注意到，树剖的本质仍然是一种 dfs 序，只不过进行了一些合法的调整。因此，子树内所有节点的 dfs 序仍然连续，因此也可以使用普通的 dfs 序线段树维护。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 1E5 + 10;

struct Edge {
    int v;
    int next;
} pool[2 * N];
int nn, head[N];

void addEdge(int u, int v) {
    pool[++nn] = {v, head[u]};
    head[u] = nn;
}

int n, m, rt, MOD;
int a[N];
int fa[N], sz[N], son[N], top[N], dep[N];

// 维护 sz[u], son[u]
void dfs1(int u, int f) {
    fa[u] = f;
    sz[u] = 1;
    dep[u] = dep[f] + 1;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(son[u] == 0 || sz[v] > sz[son[u]]) {
            son[u] = v;
        }
    }
}

int dfn[N], id[N], dt;

// 记录 dfs 序
void dfs2(int u, int f, int tp) {
    dfn[u] = ++dt;
    id[dt] = u;
    top[u] = tp;
    if(son[u]) dfs2(son[u], u, tp);
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == f) continue;
        if(v == son[u]) continue;
        dfs2(v, u, v);
    }
}

namespace seg_tree {

    int sum[4 * N], tag[4 * N];

    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }

    void push_up(int p) {
        sum[p] = (sum[lc(p)] + sum[rc(p)]) % MOD;
    }

    void move_tag(int p, int l, int r, int tg) {
        sum[p] = (sum[p] + tg * (r - l + 1)) % MOD;
        tag[p] = (tag[p] + tg) % MOD;
    }

    void push_down(int p, int l, int r) {
        int mid = (l + r) >> 1;
        move_tag(lc(p), l, mid, tag[p]);
        move_tag(rc(p), mid + 1, r, tag[p]);
        tag[p] = 0;
    }

    void build_tree(int p, int l, int r) {
        if(l == r) {
            move_tag(p, l, r, a[id[l]]);
            return;
        }
        int mid = (l + r) >> 1;
        build_tree(lc(p), l, mid);
        build_tree(rc(p), mid + 1, r);
        push_up(p);
    }

    void modify(int p, int l, int r, int ql, int qr, int val) {
        if(ql <= l && r <= qr) {
            move_tag(p, l, r, val);
            return;
        }
        int mid = (l + r) >> 1;
        push_down(p, l, r);
        if(mid >= ql) modify(lc(p), l, mid, ql, qr, val);
        if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, val);
        push_up(p);
    }

    int query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) {
            return sum[p];
        }
        int mid = (l + r) >> 1, res = 0;
        push_down(p, l, r);
        if(mid >= ql) res += query(lc(p), l, mid, ql, qr);
        if(mid < qr) res += query(rc(p), mid + 1, r, ql, qr);
        return res % MOD;
    }

}

void modify_path(int x, int y, int v) {
    while(true) {
        if(top[x] == top[y]) {
            seg_tree::modify(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), v);
            break;
        }
        if(dep[top[x]] > dep[top[y]]) {
            seg_tree::modify(1, 1, n, dfn[top[x]], dfn[x], v);
            x = fa[top[x]];
        } else {
            seg_tree::modify(1, 1, n, dfn[top[y]], dfn[y], v);
            y = fa[top[y]];
        }
    }
}

int query_path(int x, int y) {
    int res = 0;
    while(true) {
        if(top[x] == top[y]) {
            res += seg_tree::query(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]));
            res %= MOD;
            break;
        }
        if(dep[top[x]] > dep[top[y]]) {
            res += seg_tree::query(1, 1, n, dfn[top[x]], dfn[x]);
            res %= MOD;
            x = fa[top[x]];
        } else {
            res += seg_tree::query(1, 1, n, dfn[top[y]], dfn[y]);
            res %= MOD;
            y = fa[top[y]];
        }
    }
    return res;
}

void modify_tree(int x, int v) {
    seg_tree::modify(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, v);
}

int query_tree(int x) {
    return seg_tree::query(1, 1, n, dfn[x], dfn[x] + sz[x] - 1);
}

signed main() {

    cin >> n >> m >> rt >> MOD;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs1(rt, 0);
    dfs2(rt, 0, rt);

seg_tree::build_tree(1, 1, n);

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

    return 0;
}