树链剖分（HLD）

id: hld
一句话算法

树链剖分先让重儿子连续编号，把树上路径拆成 O(log⁡n)O(\log n) 段数组区间，再交给线段树处理。

阅读前建议先掌握 [ Rbook: DFS序] 和 [ Rbook: 区间更新]。本文先讲重链剖分如何编号、拆路径，再给出可复用模板与完整程序。

1 问题模型

本文讨论重链剖分：树的边不变，根在预处理前确定。给定一棵 nn 个点的有根树，每个点有权值，要求支持：

  • 树上两点路径加；
  • 树上两点路径求和；
  • 某个子树整体加；
  • 某个子树求和。

树上路径不是数组区间，不能直接套线段树。树链剖分的目标是把树上的路径拆成少量连续区间。

2 核心直觉

树剖只做一件核心的事：

DFS 编号时，永远优先走重儿子。

重儿子是子树节点数最多的儿子，不是编号最大或深度最大的儿子。并列时任选一个，叶子没有重儿子。连向重儿子的边叫重边，其余父子边叫轻边；由重边连接的极大路径叫重链，单独的点也可以是一条链。

普通 DFS 序已经能把子树变成区间，但任意路径仍可能零散。我们只改变访问儿子的顺序：先把重儿子一路走到底，再处理沿途留下的轻子树。这样一来，重链也连续了。

粗实线表示重边，虚线表示轻边；重链 1、3、4 在 DFS 序中占据前三位

图中根为 1，sz[3]=3 > sz[2]=1，所以 son[1]=3；4、5 的子树同样大，这里选 4。三条重链是 1→3→4、5、2。下面始终使用这一种合法编号：

原节点 u 1 3 4 5 2
dfn[u] 1 2 3 4 5
top[u] 1 1 1 5 2

注意，dfn 是位置，节点权值应写到 base[dfn[u]] = a[u]，线段树维护的是这份重排后的数组。

树上重链：1 -> 3 -> 4
DFS 编号：1    2    3

路径查询时，如果两个点不在同一条重链，就把更深的链头到当前点这一段处理掉，然后跳到链头的父亲。每跳一次都跨过一条轻边，而轻边最多跨 O(log⁡n)O(\log n) 次。

3 关键数组

  • fa[u]：父亲；
  • dep[u]：深度；
  • sz[u]：子树大小；
  • son[u]：重儿子；
  • top[u]：当前重链的链头；
  • dfn[u]：DFS 新编号；
  • rev[dfn]：新编号对应的原节点。

子树也会变成连续区间：

u 的子树⟺[dfn[u], dfn[u]+sz[u]−1] u\text{ 的子树} \Longleftrightarrow [dfn[u],\ dfn[u]+sz[u]-1]

4 看看剖分后的树

选择示例数据后会自动生成划分；自定义数据输入完成后点击「生成划分」。上方树图的节点内只显示原编号，黑色粗实线表示重边，灰色细虚线表示轻边；下方属性表列出每个节点的 top、size（即 sz）、son（重儿子）和 dfn。

点击节点或表格中的编号，双圈会标出选中节点，灰底标出它所在的重链；切换到「它的子树」，再对照下方的 dfn 序列，观察子树如何占据连续区间。也可以展开「查看 / 自定义树数据」，输入自己的树或修改根节点。图中采用 tidy tree 布局，沿重边相连的节点构成重链，不要求画成竖直的一条线。

交互动画加载中...

5 算法步骤

5.1 第一次 DFS

  1. 计算 fa[u]、dep[u]。
  2. 统计 sz[u]。
  3. 找到子树最大的儿子，记为 son[u]。

5.2 第二次 DFS

  1. 从链头开始给节点分配 dfn。
  2. 优先递归重儿子，让重链编号连续。
  3. 再递归所有轻儿子，每个轻儿子开启一条新链。

5.3 从递归步骤到竞赛模板

常见递归写法是 dfs1 统计大小、dfs2 重儿子优先编号。两份模板都用全局数组（Python 用列表）和独立函数，并用循环完成相同的依赖关系：

  1. 生成父亲在儿子前面的 order，记录 fa、dep。
  2. 倒着扫描 order，这时所有儿子的 sz 已知，可以计算父亲的 sz、son。
  3. 用栈做真正的 DFS：先压轻儿子，再压重儿子。栈后进先出，所以重儿子最先访问；轻儿子令 top[v]=v，重儿子继承 top[u]。

第一遍的 order 只用于统计大小，不能当作最终的 dfn。第二遍才负责生成重儿子优先的 DFS 序。链形树有 nn 层，两种语言均避免了树遍历的深递归；线段树仍使用深度 O(log⁡n)O(\log n) 的递归。

5.4 路径操作

处理路径 (u, v)：

  1. 当 top[u] != top[v]：
    • 选择链头更深的一边；
    • 在线段树上处理 [dfn[top[u]], dfn[u]]；
    • 令 u = fa[top[u]]。
  2. 最后两点在同一条重链上，交换端点使 dep[u] <= dep[v]，再处理 [dfn[u], dfn[v]]。

路径 2 到 4 先取节点 2 所在的区间，再取重链上的节点 1、3、4，子树 3 对应位置 2 到 4

例如路径 2→1→3→4：top[2]=2 比 top[4]=1 更深，先处理 [5,5]，令 u=fa[2]=1；此时与 4 同链，处理 [1,3]。虽然节点 4 本身更深，第一步仍应该跳 2 所在的链。判断的是链头深度。

路径 4→3→5 则拆成 [4,4] 和 [2,3]。两段互不重叠，最近公共祖先 3 只算一次。

5.5 子树操作

同一张图中，节点 3 的子树是 3、4、5，对应 [2,4]。因此子树修改、查询都只需要一次区间操作：

L = dfn[u]
R = dfn[u] + sz[u] - 1

树剖只是决定区间边界。区间加、区间和由懒标记线段树完成：给长度为 len 的区间加 delta，区间和增加 delta * len，懒标记增加 delta；访问部分区间前先下传标记。

6 算法证明

核心不变量：每条重链在 DFS 序上是连续区间。

  1. 第二次 DFS 总是先访问重儿子，所以从链头沿重儿子一直走的节点会被连续编号。
  2. 轻儿子会开启新链，离开当前重链后才递归，因此不会插入到当前重链的编号中间。
  3. 子树是普通 DFS 序的连续区间，优先重儿子不会破坏 DFS 序的子树连续性。

为什么跳链不会漏点或越过 LCA？

循环保持：未处理的部分恰好是当前 u 到 v 的简单路径。设 t=top[u] 是两个链头中较深的一个。若 LCA 位于 t 或 t 下方，则 v 也在 t 的子树内；v 要么与 u 同链，要么其链头比 t 更深，都与当前选择矛盾。因此 [t,u] 完全属于待处理路径，可以整段取走。

取走后，从 fa[t] 继续，既不重复链头，也不会漏掉链头上方的点。每一步都缩短未处理路径；同链时浅端点就是 LCA，最后一次区间操作恰好处理剩余部分。因此所有片段不重不漏。

为什么路径只会拆成 O(log⁡n)O(\log n) 段？

设 v 是 u 的轻儿子，h 是重儿子。由于重儿子不小于轻儿子：

sz[h]⩾sz[v]⟹sz[u]⩾1+sz[h]+sz[v]>2sz[v]. sz[h] \geqslant sz[v] \quad\Longrightarrow\quad sz[u] \geqslant 1+sz[h]+sz[v] > 2sz[v].

所以沿轻边向下，子树规模不到原来的一半；沿轻边向上，子树规模超过原来的两倍。即使多个儿子并列最大，这个不等式仍成立。

沿着轻边向上跳时，子树规模至少翻倍：

1, 2, 4, 8, ⋯ , n 1,\ 2,\ 4,\ 8,\ \cdots,\ n

因此任意点到根最多跨 O(log⁡n)O(\log n) 条轻边。一般路径可以在 LCA 处分为两条向上的路径，两边相加仍是 O(log⁡n)O(\log n) 段。

7 复杂度分析

预处理两次 DFS：

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(n)O(n)。

每次路径修改或路径查询：

  • 拆成 O(log⁡n)O(\log n) 段；
  • 每段在线段树上操作 O(log⁡n)O(\log n)；
  • 总时间复杂度：O(log⁡2n)O(\log^2 n)。

子树修改和子树查询是一次线段树区间操作，时间复杂度 O(log⁡n)O(\log n)。

8 代码模板

两份模板提供相同接口，不使用 struct 或 class。数组下标和区间端点都从 1 开始，所有区间均为闭区间。

接口 用途
init(n, mod) 清空邻接表；每组数据重新调用。其余数组由 build 逐点覆写，不需要手工清零
a[u]、add_edge(u,v) 设置初值、添加无向边
build(root) 固定根，预处理并建立线段树；每次初始化后调用一次
path_add(u,v,delta) / path_sum(u,v) 路径加 / 路径和，包含两个端点
subtree_add(u,delta) / subtree_sum(u) 子树加 / 子树和，包含 u
lca(u,v) 只跳链求 LCA，O(log⁡n)O(\log n)

C++ 版使用定长全局数组，maxn 按题目约束调整，且必须满足 n⩽maxnn \leqslant maxn：tr、lazy 占用 4 * maxn 个 long long，maxn 开到 10610^6 时这两个数组约需 64MB。Python 版按 nn 动态建列表，没有这个限制。

要求输入是一棵连通树，n⩾1n \geqslant 1，root 在 1..n 内。模板处理取模后的和；初值和增量可以是负数，输出统一落在 [0,mod-1]。C++ 约定 1⩽mod⩽231−11 \leqslant mod \leqslant 2^{31}-1，初值和增量在 long long 范围内，乘法使用 long long。不取模的问题需要同步修改线段树与路径累加处，并检查和及乘积的范围。

Python 版本兼容 Python 3.8+，无需提高递归上限。大数据仍需结合评测时限和内存限制选择语言。

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

// 节点与区间均为 1 下标；init -> 填 a / 加边 -> build -> 操作。
// n >= 1，1 <= mod <= 2^31-1；所有权值、增量用 long long。
const int maxn = 100000 + 5;  // 按题目规模调整，n 不能超过 maxn

int n, mod;
vector<int> g[maxn];
int fa[maxn], dep[maxn], sz[maxn], son[maxn], top[maxn], dfn[maxn], rev[maxn];
ll a[maxn], base[maxn], tr[maxn << 2], lazy[maxn << 2];

ll norm(ll x) { return (x % mod + mod) % mod; }

// 多组数据只需要清邻接表：旧边必须走。
// 其余数组在 build() / seg_build() 里逐点重新赋值，旧值不会影响结果。
void init(int count, int modulus) {
    n = count; mod = modulus;
    for (int u = 1; u <= n; ++u) g[u].clear();
}

void add_edge(int u, int v) {
    g[u].push_back(v); g[v].push_back(u);
}

void apply(int u, int l, int r, long long value) {
    value = norm(value);
    tr[u] = (tr[u] + value * (r - l + 1)) % mod;
    lazy[u] = (lazy[u] + value) % mod;
}

void pushdown(int u, int l, int r) {
    if (lazy[u] == 0 || l == r) return;
    int mid = (l + r) >> 1;
    apply(u << 1, l, mid, lazy[u]);
    apply(u << 1 | 1, mid + 1, r, lazy[u]);
    lazy[u] = 0;
}

void seg_build(int u, int l, int r) {
    lazy[u] = 0;  // 建树时顺手清懒标记，init 就不必整体清零
    if (l == r) {
        tr[u] = norm(base[l]);
        return;
    }
    int mid = (l + r) >> 1;
    seg_build(u << 1, l, mid);
    seg_build(u << 1 | 1, mid + 1, r);
    tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod;
}

void range_add(int ql, int qr, long long value, int u, int l, int r) {
    if (ql <= l && r <= qr) {
        apply(u, l, r, value);
        return;
    }
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) range_add(ql, qr, value, u << 1, l, mid);
    if (qr > mid) range_add(ql, qr, value, u << 1 | 1, mid + 1, r);
    tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod;
}

long long range_sum(int ql, int qr, int u, int l, int r) {
    if (ql <= l && r <= qr) return tr[u];
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    long long answer = 0;
    if (ql <= mid) answer += range_sum(ql, qr, u << 1, l, mid);
    if (qr > mid) answer += range_sum(ql, qr, u << 1 | 1, mid + 1, r);
    return answer % mod;
}

// 第一遍：先记录父亲在前的顺序，再逆序汇总子树信息。
// 第二遍：显式栈模拟重儿子优先 DFS，避免链形树的 O(n) 递归栈。
void build(int root) {
    static int order[maxn], stk[maxn];
    int cnt = 0;
    order[cnt++] = root;
    fa[root] = 0; dep[root] = 1;  // 显式写根父亲，不依赖 fa 的预清零
    for (int i = 0; i < cnt; ++i) {
        int u = order[i];
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            fa[v] = u; dep[v] = dep[u] + 1;
            order[cnt++] = v;
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        sz[u] = 1; son[u] = 0;
        int best = 0, best_size = 0;  // 局部变量比较，不依赖 son[] 的旧值
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            sz[u] += sz[v];
            if (sz[v] > best_size) { best_size = sz[v]; best = v; }
        }
        son[u] = best;
    }
    int timer = 0, tp = 0;
    stk[tp++] = root;
    top[root] = root;
    while (tp > 0) {
        int u = stk[--tp];
        dfn[u] = ++timer; rev[timer] = u; base[timer] = a[u];
        // 轻儿子先入栈，重儿子后入栈，故重儿子先被访问。
        for (int v : g[u]) {
            if (v == fa[u] || v == son[u]) continue;
            top[v] = v; stk[tp++] = v;
        }
        if (son[u]) {
            top[son[u]] = top[u]; stk[tp++] = son[u];
        }
    }
    seg_build(1, 1, n);
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

void path_add(int u, int v, long long delta) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        range_add(dfn[top[u]], dfn[u], delta, 1, 1, n);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    range_add(dfn[u], dfn[v], delta, 1, 1, n);
}

long long path_sum(int u, int v) {
    long long answer = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        answer += range_sum(dfn[top[u]], dfn[u], 1, 1, n);
        answer %= mod;
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    answer += range_sum(dfn[u], dfn[v], 1, 1, n);
    return answer % mod;
}

void subtree_add(int u, long long delta) {
    range_add(dfn[u], dfn[u] + sz[u] - 1, delta, 1, 1, n);
}

long long subtree_sum(int u) {
    return range_sum(dfn[u], dfn[u] + sz[u] - 1, 1, 1, n);
}

# Python 3.8+；全局列表与函数。节点、区间均为 1 下标。
# init(n, mod) -> 填 a / add_edge -> build(root) -> 路径与子树操作。
# 一次维护一棵静态树；新数据必须重新 init。mod 为正整数。

def init(count, modulus):
    global n, mod, g, fa, dep, sz, son, top, dfn, rev, a, base, tr, lazy
    n, mod = count, modulus
    g = [[] for _ in range(n + 1)]
    fa = [0] * (n + 1)
    dep = [0] * (n + 1)
    sz = [0] * (n + 1)
    son = [0] * (n + 1)
    top = [0] * (n + 1)
    dfn = [0] * (n + 1)
    rev = [0] * (n + 1)
    a = [0] * (n + 1)
    base = [0] * (n + 1)
    tr = [0] * (4 * n + 5)
    lazy = [0] * (4 * n + 5)


def add_edge(u, v):
    g[u].append(v)
    g[v].append(u)


def apply(u, l, r, a):
    a %= mod
    # 区间长度是 r - l + 1；先取模再加，防止数值无限增长。
    tr[u] = (tr[u] + a * (r - l + 1)) % mod
    lazy[u] = (lazy[u] + a) % mod

def pushdown(u, l, r):
    # 叶节点没有儿子可下传；lazy 为 0 时无事可做。
    if lazy[u] == 0 or l == r:
        return
    mid = (l + r) >> 1  # 除以 2 向下取整
    apply(u << 1, l, mid, lazy[u])  # 左儿子编号 2u
    apply(u << 1 | 1, mid + 1, r, lazy[u])  # 右儿子编号 2u+1
    lazy[u] = 0

def seg_build(u, l, r, base):
    if l == r:
        tr[u] = base[l] % mod
        return
    mid = (l + r) >> 1
    seg_build(u << 1, l, mid, base)
    seg_build(u << 1 | 1, mid + 1, r, base)
    tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod

def range_add(ql, qr, a, u, l, r):
    if ql <= l and r <= qr:
        apply(u, l, r, a)
        return
    pushdown(u, l, r)
    mid = (l + r) >> 1
    if ql <= mid:
        range_add(ql, qr, a, u << 1, l, mid)
    if qr > mid:
        range_add(ql, qr, a, u << 1 | 1, mid + 1, r)
    tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod

def range_sum(ql, qr, u, l, r):
    if ql <= l and r <= qr:
        return tr[u]
    pushdown(u, l, r)
    mid = (l + r) >> 1
    answer = 0
    if ql <= mid:
        answer += range_sum(ql, qr, u << 1, l, mid)
    if qr > mid:
        answer += range_sum(ql, qr, u << 1 | 1, mid + 1, r)
    return answer % mod


def build(root):
    # 父亲在前，逆序时儿子的子树大小已经算好。
    order = [root]
    dep[root] = 1
    for u in order:
        for v in g[u]:
            if v == fa[u]:
                continue
            fa[v] = u
            dep[v] = dep[u] + 1
            order.append(v)
    for u in reversed(order):
        sz[u] = 1
        for v in g[u]:
            if v == fa[u]:
                continue
            sz[u] += sz[v]
            if sz[v] > sz[son[u]]:
                son[u] = v

    timer = 0
    stack = [root]
    top[root] = root
    while stack:
        u = stack.pop()
        timer += 1
        dfn[u] = timer
        rev[timer] = u
        base[timer] = a[u]
        # 后进先出：先压轻儿子，再压重儿子，保持 DFS 的子树连续性。
        for v in g[u]:
            if v == fa[u] or v == son[u]:
                continue
            top[v] = v
            stack.append(v)
        if son[u]:
            top[son[u]] = top[u]
            stack.append(son[u])
    seg_build(1, 1, n, base)


def lca(u, v):
    while top[u] != top[v]:
        if dep[top[u]] < dep[top[v]]:
            u, v = v, u
        u = fa[top[u]]
    return u if dep[u] < dep[v] else v


def path_add(u, v, delta):
    while top[u] != top[v]:
        # 处理链头更深的一边，再跨过链头上方的轻边。
        if dep[top[u]] < dep[top[v]]:
            u, v = v, u
        range_add(dfn[top[u]], dfn[u], delta, 1, 1, n)
        u = fa[top[u]]
    # 同一条链上：浅的是 LCA，区间就是 [dfn[u], dfn[v]]。
    if dep[u] > dep[v]:
        u, v = v, u
    range_add(dfn[u], dfn[v], delta, 1, 1, n)

def path_sum(u, v):
    answer = 0
    while top[u] != top[v]:
        if dep[top[u]] < dep[top[v]]:
            u, v = v, u
        answer += range_sum(dfn[top[u]], dfn[u], 1, 1, n)
        answer %= mod
        u = fa[top[u]]
    if dep[u] > dep[v]:
        u, v = v, u
    answer += range_sum(dfn[u], dfn[v], 1, 1, n)
    return answer % mod

def subtree_add(u, delta):
    range_add(dfn[u], dfn[u] + sz[u] - 1, delta, 1, 1, n)

def subtree_sum(u):
    return range_sum(dfn[u], dfn[u] + sz[u] - 1, 1, 1, n)

9 完整代码

输入格式：第一行 n m root mod，第二行给出 n 个初始点权，随后 n-1 行无向边，再给出 m 行操作：

  • 1 x y z：路径 x 到 y 的点权加 z。
  • 2 x y：输出路径和对 mod 取模的结果。
  • 3 x z：以固定根为准，子树 x 的点权加 z。
  • 4 x：输出子树和对 mod 取模的结果。

以下程序包含模板和读入输出，可独立运行。Python 按行读取，初始权值需放在同一行。

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

// 节点与区间均为 1 下标；init -> 填 a / 加边 -> build -> 操作。
// n >= 1，1 <= mod <= 2^31-1；所有权值、增量用 long long。
const int maxn = 100000 + 5;  // 按题目规模调整，n 不能超过 maxn

int n, mod;
vector<int> g[maxn];
int fa[maxn], dep[maxn], sz[maxn], son[maxn], top[maxn], dfn[maxn], rev[maxn];
ll a[maxn], base[maxn], tr[maxn << 2], lazy[maxn << 2];

ll norm(ll x) { return (x % mod + mod) % mod; }

// 多组数据只需要清邻接表：旧边必须走。
// 其余数组在 build() / seg_build() 里逐点重新赋值，旧值不会影响结果。
void init(int count, int modulus) {
    n = count; mod = modulus;
    for (int u = 1; u <= n; ++u) g[u].clear();
}

void add_edge(int u, int v) {
    g[u].push_back(v); g[v].push_back(u);
}

void apply(int u, int l, int r, long long value) {
    value = norm(value);
    tr[u] = (tr[u] + value * (r - l + 1)) % mod;
    lazy[u] = (lazy[u] + value) % mod;
}

void pushdown(int u, int l, int r) {
    if (lazy[u] == 0 || l == r) return;
    int mid = (l + r) >> 1;
    apply(u << 1, l, mid, lazy[u]);
    apply(u << 1 | 1, mid + 1, r, lazy[u]);
    lazy[u] = 0;
}

void seg_build(int u, int l, int r) {
    lazy[u] = 0;  // 建树时顺手清懒标记，init 就不必整体清零
    if (l == r) {
        tr[u] = norm(base[l]);
        return;
    }
    int mid = (l + r) >> 1;
    seg_build(u << 1, l, mid);
    seg_build(u << 1 | 1, mid + 1, r);
    tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod;
}

void range_add(int ql, int qr, long long value, int u, int l, int r) {
    if (ql <= l && r <= qr) {
        apply(u, l, r, value);
        return;
    }
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) range_add(ql, qr, value, u << 1, l, mid);
    if (qr > mid) range_add(ql, qr, value, u << 1 | 1, mid + 1, r);
    tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod;
}

long long range_sum(int ql, int qr, int u, int l, int r) {
    if (ql <= l && r <= qr) return tr[u];
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    long long answer = 0;
    if (ql <= mid) answer += range_sum(ql, qr, u << 1, l, mid);
    if (qr > mid) answer += range_sum(ql, qr, u << 1 | 1, mid + 1, r);
    return answer % mod;
}

// 第一遍：先记录父亲在前的顺序，再逆序汇总子树信息。
// 第二遍：显式栈模拟重儿子优先 DFS，避免链形树的 O(n) 递归栈。
void build(int root) {
    static int order[maxn], stk[maxn];
    int cnt = 0;
    order[cnt++] = root;
    fa[root] = 0; dep[root] = 1;  // 显式写根父亲，不依赖 fa 的预清零
    for (int i = 0; i < cnt; ++i) {
        int u = order[i];
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            fa[v] = u; dep[v] = dep[u] + 1;
            order[cnt++] = v;
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        sz[u] = 1; son[u] = 0;
        int best = 0, best_size = 0;  // 局部变量比较，不依赖 son[] 的旧值
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            sz[u] += sz[v];
            if (sz[v] > best_size) { best_size = sz[v]; best = v; }
        }
        son[u] = best;
    }
    int timer = 0, tp = 0;
    stk[tp++] = root;
    top[root] = root;
    while (tp > 0) {
        int u = stk[--tp];
        dfn[u] = ++timer; rev[timer] = u; base[timer] = a[u];
        // 轻儿子先入栈，重儿子后入栈，故重儿子先被访问。
        for (int v : g[u]) {
            if (v == fa[u] || v == son[u]) continue;
            top[v] = v; stk[tp++] = v;
        }
        if (son[u]) {
            top[son[u]] = top[u]; stk[tp++] = son[u];
        }
    }
    seg_build(1, 1, n);
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

void path_add(int u, int v, long long delta) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        range_add(dfn[top[u]], dfn[u], delta, 1, 1, n);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    range_add(dfn[u], dfn[v], delta, 1, 1, n);
}

long long path_sum(int u, int v) {
    long long answer = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        answer += range_sum(dfn[top[u]], dfn[u], 1, 1, n);
        answer %= mod;
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    answer += range_sum(dfn[u], dfn[v], 1, 1, n);
    return answer % mod;
}

void subtree_add(int u, long long delta) {
    range_add(dfn[u], dfn[u] + sz[u] - 1, delta, 1, 1, n);
}

long long subtree_sum(int u) {
    return range_sum(dfn[u], dfn[u] + sz[u] - 1, 1, 1, n);
}


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

    int count, m, root, modulus;
    cin >> count >> m >> root >> modulus;

    init(count, modulus);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = norm(a[i]);
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    build(root);

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            long long z;
            cin >> x >> y >> z;
            path_add(x, y, z);
        } else if (op == 2) {
            int x, y;
            cin >> x >> y;
            cout << path_sum(x, y) << '\n';
        } else if (op == 3) {
            int x;
            long long z;
            cin >> x >> z;
            subtree_add(x, z);
        } else {
            int x;
            cin >> x;
            cout << subtree_sum(x) << '\n';
        }
    }

    return 0;
}

# Python 3.8+；全局列表与函数。节点、区间均为 1 下标。
# init(n, mod) -> 填 a / add_edge -> build(root) -> 路径与子树操作。
# 一次维护一棵静态树；新数据必须重新 init。mod 为正整数。

def init(count, modulus):
    global n, mod, g, fa, dep, sz, son, top, dfn, rev, a, base, tr, lazy
    n, mod = count, modulus
    g = [[] for _ in range(n + 1)]
    fa = [0] * (n + 1)
    dep = [0] * (n + 1)
    sz = [0] * (n + 1)
    son = [0] * (n + 1)
    top = [0] * (n + 1)
    dfn = [0] * (n + 1)
    rev = [0] * (n + 1)
    a = [0] * (n + 1)
    base = [0] * (n + 1)
    tr = [0] * (4 * n + 5)
    lazy = [0] * (4 * n + 5)


def add_edge(u, v):
    g[u].append(v)
    g[v].append(u)


def apply(u, l, r, a):
    a %= mod
    # 区间长度是 r - l + 1；先取模再加，防止数值无限增长。
    tr[u] = (tr[u] + a * (r - l + 1)) % mod
    lazy[u] = (lazy[u] + a) % mod

def pushdown(u, l, r):
    # 叶节点没有儿子可下传；lazy 为 0 时无事可做。
    if lazy[u] == 0 or l == r:
        return
    mid = (l + r) >> 1  # 除以 2 向下取整
    apply(u << 1, l, mid, lazy[u])  # 左儿子编号 2u
    apply(u << 1 | 1, mid + 1, r, lazy[u])  # 右儿子编号 2u+1
    lazy[u] = 0

def seg_build(u, l, r, base):
    if l == r:
        tr[u] = base[l] % mod
        return
    mid = (l + r) >> 1
    seg_build(u << 1, l, mid, base)
    seg_build(u << 1 | 1, mid + 1, r, base)
    tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod

def range_add(ql, qr, a, u, l, r):
    if ql <= l and r <= qr:
        apply(u, l, r, a)
        return
    pushdown(u, l, r)
    mid = (l + r) >> 1
    if ql <= mid:
        range_add(ql, qr, a, u << 1, l, mid)
    if qr > mid:
        range_add(ql, qr, a, u << 1 | 1, mid + 1, r)
    tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod

def range_sum(ql, qr, u, l, r):
    if ql <= l and r <= qr:
        return tr[u]
    pushdown(u, l, r)
    mid = (l + r) >> 1
    answer = 0
    if ql <= mid:
        answer += range_sum(ql, qr, u << 1, l, mid)
    if qr > mid:
        answer += range_sum(ql, qr, u << 1 | 1, mid + 1, r)
    return answer % mod


def build(root):
    # 父亲在前，逆序时儿子的子树大小已经算好。
    order = [root]
    dep[root] = 1
    for u in order:
        for v in g[u]:
            if v == fa[u]:
                continue
            fa[v] = u
            dep[v] = dep[u] + 1
            order.append(v)
    for u in reversed(order):
        sz[u] = 1
        for v in g[u]:
            if v == fa[u]:
                continue
            sz[u] += sz[v]
            if sz[v] > sz[son[u]]:
                son[u] = v

    timer = 0
    stack = [root]
    top[root] = root
    while stack:
        u = stack.pop()
        timer += 1
        dfn[u] = timer
        rev[timer] = u
        base[timer] = a[u]
        # 后进先出：先压轻儿子，再压重儿子，保持 DFS 的子树连续性。
        for v in g[u]:
            if v == fa[u] or v == son[u]:
                continue
            top[v] = v
            stack.append(v)
        if son[u]:
            top[son[u]] = top[u]
            stack.append(son[u])
    seg_build(1, 1, n, base)


def lca(u, v):
    while top[u] != top[v]:
        if dep[top[u]] < dep[top[v]]:
            u, v = v, u
        u = fa[top[u]]
    return u if dep[u] < dep[v] else v


def path_add(u, v, delta):
    while top[u] != top[v]:
        # 处理链头更深的一边，再跨过链头上方的轻边。
        if dep[top[u]] < dep[top[v]]:
            u, v = v, u
        range_add(dfn[top[u]], dfn[u], delta, 1, 1, n)
        u = fa[top[u]]
    # 同一条链上：浅的是 LCA，区间就是 [dfn[u], dfn[v]]。
    if dep[u] > dep[v]:
        u, v = v, u
    range_add(dfn[u], dfn[v], delta, 1, 1, n)

def path_sum(u, v):
    answer = 0
    while top[u] != top[v]:
        if dep[top[u]] < dep[top[v]]:
            u, v = v, u
        answer += range_sum(dfn[top[u]], dfn[u], 1, 1, n)
        answer %= mod
        u = fa[top[u]]
    if dep[u] > dep[v]:
        u, v = v, u
    answer += range_sum(dfn[u], dfn[v], 1, 1, n)
    return answer % mod

def subtree_add(u, delta):
    range_add(dfn[u], dfn[u] + sz[u] - 1, delta, 1, 1, n)

def subtree_sum(u):
    return range_sum(dfn[u], dfn[u] + sz[u] - 1, 1, 1, n)


def main():
    import sys
    # 按行读取，避免一次 split 整份输入产生大量临时对象。
    read = sys.stdin.buffer.readline
    count, m, root, modulus = map(int, read().split())
    init(count, modulus)
    a[1:] = list(map(int, read().split()))
    for _ in range(n - 1):
        u, v = map(int, read().split())
        add_edge(u, v)
    build(root)
    out = []
    for _ in range(m):
        op, *args = map(int, read().split())
        if op == 1:
            path_add(*args)
        elif op == 2:
            out.append(str(path_sum(*args)))
        elif op == 3:
            subtree_add(*args)
        else:
            out.append(str(subtree_sum(*args)))
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

10 测试用例

输入：

5 5 1 100
1 2 3 4 5
1 2
1 3
3 4
3 5
2 4 5
1 2 4 1
2 4 5
3 3 2
4 3

输出：

12
14
20

解释：

  • 初始路径 4 -> 3 -> 5 的和为 4 + 3 + 5 = 12；
  • 路径 2 -> 4 加 1 后，点 1,2,3,4 都增加；
  • 子树 3 加 2 后，点 3,4,5 都增加，子树和变为 20。

10.1 单点与负增量

1 5 1 7
3
2 1 1
1 1 1 -5
4 1
3 1 9
2 1 1

输出为 3、5、0（各占一行）。u=v 时点权查询仍包含这个点；mod=1 时所有输出都应为 0。

11 边权、方向与易错点

边权转点权。 把边 (fa[x],x) 的权值存到较深的端点 x，根的位置放 0。跳链阶段仍处理 [dfn[top[u]],dfn[u]]，因为链头保存的正是本次跨过的轻边权。最后同链时，设 u 较浅，只处理 [dfn[u]+1,dfn[v]]，排除 LCA 保存的那条路径外的边。空区间直接跳过；u=v 的边权和为 0。查询子树内部的边也要排除子树根位置。本文代码默认点权，切换模型时需修改这些边界。

非交换信息。 和、最大值不在意片段顺序；字符串、矩阵乘法、颜色段却在意路径方向。此时要分别累计原起点侧和终点侧，在线段树里维护区间正向与反向信息，再按路径顺序合并，不能直接照搬 path_sum 的累加方式。

常见错误。 比较 dep[top[u]]，不是 dep[u]；跳到 fa[top[u]]，不是 fa[u] 或 top[u]；在线段树上使用 dfn，不是原编号。不要把“在同一条重链”写成“两点深度相同”。

仅有子树操作时，普通 DFS 序就足够；只有 LCA 查询时，可以只保留树剖数组与 lca，不需要线段树。树剖预处理依赖固定边结构，直接增删边会使编号失效。

12 应用分类详解

树链剖分的本质是把树上路径转成少量数组区间。只要题目要求频繁操作树上路径，就应该考虑树剖。

一、 路径修改和路径查询

典型模式： 两点之间路径加、路径求和、路径最大值。

识别信号： 出现“uu 到 vv 的路径上所有点/边”并且操作次数很多。

核心建模： 用树剖拆路径，用线段树维护区间信息。

应用场景 经典题目 核心思路
树剖模板 [ luogu P3384: 【模板】重链剖分 / 树链剖分] 路径和 + 子树和
树上路径最大值 [ luogu P2590: [ZJOI2008] 树的统计] 线段树维护最大值

二、 子树整体操作

典型模式： 修改某个点的整棵子树，或查询子树权值和。

识别信号： 出现“以 uu 为根的子树”。

核心建模： 子树在 DFS 序中是连续区间 [dfn[u], dfn[u]+size[u]-1]。

应用场景 经典题目 核心思路
子树加与子树求和 [ luogu P3384: 【模板】重链剖分 / 树链剖分] DFS 序区间操作
树上统计 子树贡献类题目 把子树压成数组区间

三、 路径拆分后的复合维护

典型模式： 线段树节点维护的不只是和，还可能是最大值、最小值、颜色段、矩阵等。

识别信号： 路径信息能通过区间合并得到。

核心建模： 树剖只负责拆路径；真正维护什么信息由线段树决定。

13 经典例题

1. [ luogu P3384: 【模板】重链剖分 / 树链剖分]

树链剖分模板题，完整覆盖路径加、路径和、子树加、子树和。

2. [ luogu P2590: [ZJOI2008] 树的统计]

练习单点赋值、路径求和与路径最大值：线段树同时维护和与最大值。最大值不取模，查询单位元应设为负无穷，避免全负权时错误返回 0。

3. [ luogu P4114]

路径最大边权类问题。适合练习边权转点权，以及路径查询时如何排除 LCA 点。

14 相关阅读