本文共 4908 字，大约阅读时间需要 16 分钟。

模板：轻重链剖分

基本概念

在轻重链剖分中，我们需要明确一些关键概念：

重链及其dfs序的计算

通过两个深度优先遍历（DFS），我们可以高效地完成该任务：

第一个DFS的目标

• 标记结点的父亲 (fa数组)。
• 标记结点的重儿子 (son数组)。
• 标记结点的深度 (dep数组)。
• 标记结点的大小 (siz数组)。

第二个DFS的目标

• 为什么需要进行第二遍 DFS？因为第一个 DFS 需要确定结点的重儿子。

  • 标记重链的开始结点 (top数组)。
  • 记录结点的权值顺序 (dfn数组)，并与时间戳结合使用。

示例分析

在下面的示例中，我们可以看到：

• 第一条重链：FHKL，重链的起始结点为 F。
• 第二条重链：CD，重链的起始结点为 C。

通过标记重链的起始结点，我们可以轻松判断两个结点是否属于同一重链。

如果两个结点不在同一重链上，我们可以通过维护指针来实现：

• 指针操作：不断让顶部结点沿着重链向上跳，同时在线段树上进行更新。
• 终止条件：当两个指针指向同一结点时，停止操作。

引理

除了根节点外，任何一个结点的父节点都位于一条重链上。这是因为父节点至少有一个儿子，而该儿子就是重儿子，从而位于一条重链。

路径分类

对于任意两个结点 x 和 y：

代码实现

以下是一个简化的代码实现示例：

#pragma GCC optimize("Ofast","inline")#include 
   
    using namespace std;const int maxn = 1e6 + 10;int mod = 998244353;struct edge {    int to, next;};int tot, head[maxn];void init() {    memset(head, -1, sizeof(head));}void adde(int u, int v) {    edge[tot].to = v;    edge[tot].next = head[u];    head[u] = tot++;    edge[tot].to = u;    edge[tot].next = head[v];    head[v] = tot++;}int fa[maxn], dep[maxn], siz[maxn], son[maxn];void dfs1(int u, int f) {    fa[u] = f;    dep[u] = dep[f] + 1;    siz[u] = 1;    for (int i = head[u]; ~i; i = edge[i].next) {        int v = edge[i].to;        if (v == f) continue;        dfs1(v, u);        siz[u] += siz[v];        if (siz[v] > siz[son[u]]) {            son[u] = v;        }    }}int cnt, dfn[maxn], top[maxn], w[maxn];void dfs2(int u, int t) {    dfn[u] = ++cnt;    top[u] = t;    w[cnt] = v[u];    if (!son[u]) return;    dfs2(son[u], t);    for (int i = head[u]; ~i; i = edge[i].next) {        int v = edge[i].to;        if (v == fa[u] || v == son[u]) continue;        dfs2(v, v);    }}int tree[maxn], lazy[maxn];void push_down(int node, int l, int r) {    lazy[node*2] += lazy[node];    lazy[node*2 + 1] += lazy[node];    int mid = (l + r) / 2;    tree[node*2] += (mid - l + 1) * lazy[node] % mod;    tree[node*2 + 1] += (r - mid) * lazy[node] % mod;    lazy[node] = 0;}void build(int node, int start, int ends) {    if (start == ends) {        tree[node] = w[start] % mod;        return;    }    int mid = (start + ends) / 2;    build(node*2, start, mid);    build(node*2 + 1, mid + 1, ends);    tree[node] = (tree[node*2] + tree[node*2 + 1]) % mod;}void update(int node, int start, int ends, int l, int r, int val) {    if (start >= l && ends <= r) {        lazy[node] += val;        tree[node] += (ends - start + 1) * val % mod;        return;    }    if (lazy[node]) push_down(node, start, ends);    int mid = (start + ends) / 2;    if (l <= mid) {        update(node*2, start, mid, l, r, val);    }    if (mid < r) {        update(node*2 + 1, mid + 1, ends, l, r, val);    }    tree[node] = (tree[node*2] + tree[node*2 + 1]) % mod;}int query(int node, int start, int ends, int l, int r) {    if (start > end) return 0;    if (lazy[node]) push_down(node, start, ends);    int mid = (start + ends) / 2;    int res = 0;    if (l <= mid) {        res += query(node*2, start, mid, l, r);    }    if (mid < r) {        res += query(node*2 + 1, mid + 1, ends, l, r);    }    return res % mod;}void mchain(int x, int y, int z) {    z %= mod;    while (top[x] != top[y]) {        if (dep[top[x]] < dep[top[y]]) swap(x, y);        update(1, 1, n, dfn[top[x]], dfn[x], z);        x = fa[top[x]];    }    if (dep[x] > dep[y]) swap(x, y);    update(1, 1, n, dfn[x], dfn[y], z);}int qchain(int x, int y) {    int ret = 0;    while (top[x] != top[y]) {        if (dep[top[x]] < dep[top[y]]) swap(x, y);        ret = (ret + query(1, 1, n, dfn[top[x]], dfn[x])) % mod;        x = fa[top[x]];    }    if (dep[x] > dep[y]) swap(x, y);    ret = (ret + query(1, 1, n, dfn[x], dfn[y])) % mod;    return ret % mod;}int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    init();    cin >> n >> m >> r >> mod;    for (int i = 1; i <= n; i++) {        cin >> v[i];    }    for (int i = 0; i < n-1; i++) {        int x, y;        cin >> x >> y;        adde(x, y);    }    dfs1(r, r);    dfs2(r, r);    build(1, 1, n);    for (int i = 0; i < m; i++) {        int opt;        cin >> opt;        if (opt == 1) {            int x, y, z;            cin >> x >> y >> z;            mchain(x, y, z);        } else if (opt == 2) {            int x, y;            cin >> x >> y;            cout << qchain(x, y) << endl;        } else if (opt == 3) {            int x, y;            cin >> x >> y;            update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, y);        } else {            int x;            cin >> x;            cout << query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) << endl;        }    }}
   

说明

• 模块化设计：代码采用模块化设计，便于维护和扩展。
• 线段树：用于处理区间查询和更新操作。
• 高效指针操作：通过指针操作和线段树更新，实现了轻重链剖分的高效处理。
• 易于扩展：代码结构清晰，便于根据需求添加新的功能和模块。

总结

通过两个DFS遍历和线段树操作，我们可以高效地处理树上的路径问题。无论是路径是否在同一重链上，还是路径的查询和更新，优化后的代码都能完成任务。这是一种高效且灵活的算法设计，能够解决复杂的路径问题。