第 53 章树链剖分：把树拆成链，让「路径」变成「区间」

1一句话问题

给一棵 n 个点的树，每个点有一个权值，然后 m 次操作，每次是下面四种之一：

1 x y z    x 到 y 的路径上，每个点 += z
2 x y      问 x 到 y 的路径上，点权之和
3 x z      x 的子树里，每个点 += z
4 x        问 x 的子树的点权和

n, m ≤ 10⁵。这就是洛谷 P3384。

输入

输出

2
21

第一行是 n m 根模数。⚠ 答案要对模数取余 —— 这一章不讲取模，但别把它忘了，忘了就是一道全 WA。

上面那段输出是仓库里的 fast.cpp 真跑出来的。

2先看清楚：难的是哪一半

四种操作里，子树那两种其实不难。

★ 「子树是一段连续区间」是任何 DFS 序都白送的

按 DFS 的进入顺序给每个点编号（记成 dfn），那么

子树 u 里的点  =  编号在 [dfn[u], dfn[u] + siz[u] - 1] 里的点

因为 DFS 进了 u 之后，要把 u 的整棵子树走完才会出来 —— 这中间编出去的号，正好就是子树里那些点，一个不多一个不少。

⇒ 于是「子树加」「子树求和」直接就是区间加和区间求和，第 39 章那棵线段树原样拿来就能用。

难的是路径那两种。 路径在编号上是散的 —— x 往上走、y 往上走，经过的点编号东一个西一个，凑不成区间。

3暴力：路径上一个点一个点爬

brute.cpp暴力

// 树链剖分那道题的暴力：路径上一个点一个点爬，子树整棵遍历
//
// 四种操作（洛谷 P3384 的四操作）：
//   1 x y z   把 x 到 y 的路径上每个点 += z
//   2 x y     问 x 到 y 的路径上点权和
//   3 x z     把以 x 为根的子树里每个点 += z
//   4 x       问以 x 为根的子树的点权和
//
// 暴力怎么做：
//   路径 —— 先把 x、y 里深的那个往上提到同深度，再一起往上走，边走边算（顺手就求了 LCA）；
//   子树 —— 从 x 出发 BFS 一遍。
//
// ★ 它**完全正确**，慢的地方也很具体：一次操作最坏碰 n 个点 ⇒ m 次就是 O(nm)。
//   ⚠ 而「最坏」是有形状的：**链**上路径就是 n 个点，随机树上只有 O(log n) 左右。
//     ⇒ 量它有多慢必须造链（见 gen.cpp 的档位）。
//
// ⚠ 用 BFS 不用递归：链上 10⁵ 层递归必爆栈（第 30、51 章都踩过这条）。

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

static int n, m, root;
static long long MOD;
static vector<int> g[100005];
static long long w[100005];
static int fa[100005], dep[100005], bfsOrder[100005];

static void build() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = root;
    fa[root] = 0; dep[root] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
}

/** 路径 x..y 上每个点做 f */
template <class F>
static void onPath(int x, int y, F f) {
    while (dep[x] > dep[y]) { f(x); x = fa[x]; }
    while (dep[y] > dep[x]) { f(y); y = fa[y]; }
    while (x != y) { f(x); f(y); x = fa[x]; y = fa[y]; }
    f(x);                                   // LCA 自己
}

/** 子树 x 里每个点做 f（BFS，不递归） */
template <class F>
static void onSubtree(int x, F f) {
    static int q[100005];
    int head = 0, tail = 0;
    q[tail++] = x;
    while (head < tail) {
        int u = q[head++];
        f(u);
        for (int v : g[u]) if (v != fa[u]) q[tail++] = v;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> root >> MOD)) return 0;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
    build();

    for (int i = 0; i < m; i++) {
        int op; cin >> op;
        if (op == 1) { int x, y; long long z; cin >> x >> y >> z; onPath(x, y, [&](int u) { w[u] = (w[u] + z) % MOD; }); }
        else if (op == 2) { int x, y; long long s = 0; cin >> x >> y; onPath(x, y, [&](int u) { s = (s + w[u]) % MOD; }); cout << s << '\n'; }
        else if (op == 3) { int x; long long z; cin >> x >> z; onSubtree(x, [&](int u) { w[u] = (w[u] + z) % MOD; }); }
        else { int x; long long s = 0; cin >> x; onSubtree(x, [&](int u) { s = (s + w[u]) % MOD; }); cout << s << '\n'; }
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

它完全正确：把深的那个往上提到同深度，再一起往上走（顺手就求了 LCA）；子树那两种就 BFS 一遍。

⚠ 注意它用的是 BFS 不是递归 —— 这一章最坏的形状就是一条 10⁵ 个点的链，递归必爆栈（第 30 章实测过：本机 8 MB 栈，DFS 到 285380 层就段错误）。

4实测：它有多慢 —— ⚠ 旋钮不是 n，是形状

⚠ 「暴力有多慢」这句话，不说形状就是没说

同样 n 个点：

随机树上，两点之间的路径平均只有 O(log n) 个点 —— 暴力一点都不慢；
一条链上，一条路径就是 n 个点 —— 一次操作就是 O(n)。

⇒ 所以量它必须造链。本机实测（链，n = m）：

`n = m`	暴力
2000	13 毫秒
4000	40 毫秒
8000	129 毫秒
16000	552 毫秒

每翻一倍，时间乘四 —— 这就是 O(nm) 的样子。按这个速率外推到 n = m = 10⁵：约 21 秒，而时限是 1 秒。

★ 对照：同一份数据（n = m = 16000 的链）正解只要 13 毫秒。

5★ 关键的一步：把树拆成链

★★★ 不是发明新结构，是换一个编号顺序

路径在编号上是散的 —— 那就换一种编号方式，让它不散。

第一步：给每个点挑一个「重儿子」= 子树最大的那个儿子。 一路顺着重儿子走下去，就得到一条重链。整棵树被这些重链铺满，谁也不重叠。

第二步：DFS 编号时，永远先走重儿子。 于是同一条重链上的点，编号是连续的一段。

⇒ 现在再看那条路径：x 往上跳，每次整条链地跳 —— 它在自己那条链上从 x 一直到链顶，这一整段编号是连续的，丢给线段树就是一次区间操作；然后从链顶的父亲接着跳下一条链。

      跳一次 = 砍掉一整段连续编号
      x ......... top[x]          <- 一段区间
                     |
                  fa[top[x]]      <- 换一条链，继续

一条路径要跳几次？—— 不超过 log2(n) 次（下一步证给你看）。 ⇒ 一次路径操作 = O(log n) 段区间 × 每段 O(log n) = O(log² n)。

6动画一：重儿子、重链、编号

剖分：重儿子、重链、dfn换一棵树

第 1 / 13 步

粗线 = 重边（连着重儿子）；一串粗线就是一条重链。右上角小字是 dfn。

还没开始：先算出每个点的子树大小和重儿子

盯住右上角那个 # 编号：每次走进重儿子，编号都接着上一格往下走；一旦拐进轻儿子，就另起一条链、也另起一段编号。

7动画二：一条路径怎么被砍成几段

跳链：一条路径被砍成几段换一条路径

第 1 / 4 步

已经砍下来 0 段

要拆的是 8 到 12 这条路径

下面那条长条是按 dfn 排开的所有点。看清楚一件事：每砍下来一段，它在长条上都是连成一片的 —— 所以才能丢给线段树。

⚠ 还要看每一步比的是什么：链顶的深度，不是点自己的深度。比错了就是第 ⑪ 步那个 wrongTop。

8★ 为什么最多跳 log2(n) 次

★ 一句话的证明：走一条轻边，子树至少翻倍

设 v 是 u 的轻儿子（不是重儿子）。那么 siz[v] ≤ siz[u] / 2 —— 否则 v 的子树就超过了一半，其他所有儿子加起来都不如它，它就该是重儿子了。

⇒ 从下往上每走一条轻边，子树大小至少翻一倍。 子树最大就是 n，所以一条根到底的路上，轻边最多 log2(n) 条。

而跳链的次数 = 路上轻边的条数 + 1（每跳一次正好跨过一条轻边）。 ⇒ 最多 ⌊log2 n⌋ + 1 段。

这句话可以直接量：

count.cpp数段数

// 换一把尺子：一条路径**被拆成了几段**
//
// 用法：./count [n]          人话版
//       ./count [n] csv      只打 `键,值`，给 check:viz 用
//
// ★ 这份程序存在的理由只有一个：**wrongHeavy.cpp 那个 bug，对拍永远抓不到。**
//   重儿子挑错（挑成「第一个儿子」而不是「子树最大的儿子」）**答案完全正确** ——
//   1800 轮六种形状全部一致。坏掉的只有复杂度，而复杂度得**数次数**才看得见。
//
// 量的是「跳链跳了几次」= 一条路径被拆成几段区间。理论上界：
//   走一条轻边，子树至少翻倍 ⇒ 根到任意点的轻边 <= log2(n) ⇒ 段数 <= log2(n) + 1。
//
// 三种形状（都是 n 个点）：
//   ① 随机树   ② 从一端生根的链   ③ ★ **梳子**：一条主链，每个链点先挂一个叶子再接主链
//      —— 第 ③ 种是专门造给 wrongHeavy 的：**每个点的「第一个儿子」都是那片叶子**，
//         于是它把整条主链的边全判成轻边，段数直接退化成 O(n)。

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

static int n;
static vector<int> g[200005];
static int fa[200005], dep[200005], siz[200005], son[200005], top_[200005], bfsOrder[200005];

static void pass1(bool byFirstChild) {
    int head = 0, tail = 0;
    bfsOrder[tail++] = 1; fa[1] = 0; dep[1] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (byFirstChild) { if (!son[p]) son[p] = u; }             // ⚠ wrongHeavy 的挑法
        else if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;      // 正确的挑法
    }
    /* byFirstChild 时「第一个」按 BFS 倒序会变成「最后一个」，这里按邻接表顺序重挑一遍 */
    if (byFirstChild) {
        for (int u = 1; u <= n; u++) {
            son[u] = 0;
            for (int v : g[u]) if (v != fa[u]) { son[u] = v; break; }
        }
    }
    for (int i = 0; i < n; i++) {
        int u = bfsOrder[i];
        top_[u] = (u == 1) ? 1 : (son[fa[u]] == u ? top_[fa[u]] : u);
    }
}

/** x..y 这条路径被拆成几段 */
static int segs(int x, int y) {
    int c = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        c++;
        x = fa[top_[x]];
    }
    return c + 1;
}

static void clearG() { for (int i = 0; i <= n + 1; i++) g[i].clear(); }

/** 三种形状：0 随机树 / 1 从一端生根的链 / 2 梳子（每个链点的第一个儿子是叶子） */
static void makeShape(int shape) {
    clearG();
    mt19937 rng(20260827u);
    if (shape == 0) {
        for (int i = 2; i <= n; i++) { int p = 1 + (int)(rng() % (unsigned)(i - 1)); g[i].push_back(p); g[p].push_back(i); }
    } else if (shape == 1) {
        for (int i = 2; i <= n; i++) { g[i].push_back(i - 1); g[i - 1].push_back(i); }
    } else {
        /* 梳子：1 - 3 - 5 - 7 …… 是主链，偶数编号都是挂在主链上的叶子。
           ⚠ 顺序很重要：先 push 叶子，再 push 下一个链点 ⇒ 「第一个儿子」永远是叶子。 */
        int last = 1;
        for (int i = 2; i + 1 <= n; i += 2) {
            g[last].push_back(i); g[i].push_back(last);            // 先挂叶子
            g[last].push_back(i + 1); g[i + 1].push_back(last);    // 再接主链
            last = i + 1;
        }
        if (n % 2 == 0) { g[last].push_back(n); g[n].push_back(last); }
    }
}

int main(int argc, char** argv) {
    n = (argc > 1) ? atoi(argv[1]) : 100000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    int lg = 0; for (int x = n; x > 0; x >>= 1) lg++;               // ⌊log2 n⌋ + 1
    const char* shapeName[3] = { "随机树", "从一端生根的链", "梳子（第一个儿子是叶子）" };
    int mx[3][2];                                                   // [形状][0=正确, 1=wrongHeavy]

    for (int shape = 0; shape < 3; shape++) {
        makeShape(shape);
        for (int bad = 0; bad < 2; bad++) {
            pass1(bad == 1);
            mt19937 q(12345u);
            int best = 0;
            for (int t = 0; t < 2000; t++) {
                int x = 1 + (int)(q() % (unsigned)n), y = 1 + (int)(q() % (unsigned)n);
                best = max(best, segs(x, y));
            }
            /* 最深那个点到根，是段数最大的候选，单独也试一次 */
            int deepest = 1;
            for (int i = 1; i <= n; i++) if (dep[i] > dep[deepest]) deepest = i;
            best = max(best, segs(1, deepest));
            mx[shape][bad] = best;
        }
    }

    if (csv) {
        printf("n,%d\nlog2n,%d\n", n, lg);
        for (int shape = 0; shape < 3; shape++)
            printf("shape%dOk,%d\nshape%dBad,%d\n", shape, mx[shape][0], shape, mx[shape][1]);
        printf("combBadOverOk,%d\n", mx[2][1] / max(1, mx[2][0]));
        return 0;
    }
    printf("n = %d（⌊log2 n⌋ + 1 = %d），一条路径最多被拆成几段：\n\n", n, lg);
    printf("  %-30s %10s %10s\n", "形状", "正确挑法", "挑第一个儿子");
    for (int shape = 0; shape < 3; shape++) {
        /* ⚠ 中文双宽，按显示宽度补空格 */
        string t = shapeName[shape];
        int wid = 0; for (unsigned char c : t) { if ((c & 0xC0) == 0x80) continue; wid += (c < 0x80) ? 1 : 2; }
        printf("  %s%*s %10d %10d\n", t.c_str(), max(0, 30 - wid), "", mx[shape][0], mx[shape][1]);
    }
    printf("\n  ★ 正确挑法那一列全都 <= %d = ⌊log2 n⌋ + 1 —— 这就是「轻边至多 log 条」那条保证。\n", lg);
    printf("  ★★★ 而梳子上挑错儿子要拆 %d 段，是正确挑法的 %d 倍 —— **答案却一个字都不差**。\n",
           mx[2][1], mx[2][1] / max(1, mx[2][0]));
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

`n = 10⁵`（`⌊log2 n⌋ + 1 = 17`）	正确挑重儿子	⚠ 挑「第一个儿子」
随机树	14	18
从一端生根的链	1	1
★ 梳子（每个点的第一个儿子是叶子）	3	★★★ 50 000

9正解

fast.cpp正解

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

// 树链剖分（重链剖分）+ 线段树 —— 正解
//
// 输入输出和 brute.cpp 完全一样，慢的那一层被换掉了：
//   暴力：一条路径一个点一个点爬，最坏 O(n)
//   这里：一条路径被拆成 O(log n) 段**连续区间**，每段丢给线段树 O(log n)
//   ⇒ 一次操作 O(log²n)。
//
// ============ 两趟遍历分别在算什么 ============
//
//   第一趟：fa / dep / siz / son
//     son[u] = u 的**重儿子** = 子树最大的那个儿子。
//     ⚠ **并列时挑谁不影响正确性**（挑谁都还是一条合法的重链剖分），
//       但它影响 dfn 的具体样子 —— 而动画那份 TS 要和这里**逐字节一致**，
//       所以两边都得是同一条规则：倒着扫 BFS 序、严格大于才换 ⇒ **编号靠后的那个赢**。
//
//   第二趟：top / dfn
//     **重儿子优先**地编号 ⇒ 一条重链上的 dfn 是**连续的一段**。
//     top[u] = u 所在重链最顶上那个点。
//
// ⇒ 于是两件事同时成立：
//     子树 = 区间 [dfn[u], dfn[u] + siz[u] - 1]      ← 任何 DFS 序都白送这一条
//     路径 = O(log n) 段区间                          ← 这一条只有「重儿子优先」才有
//
// ★ 为什么是 log：从 u 往上走一条**轻边**，子树大小至少翻倍
//   （轻儿子的子树 < 父亲子树的一半，否则它就该是重儿子）。
//   n 最多翻 log2(n) 次 ⇒ 根到任意点的轻边不超过 log2(n) 条 ⇒ 最多跳 log2(n)+1 条链。
//   ⇒ 这句话是**可以实测**的，见 count.cpp 那张「链 / 菊花 / 随机树」的表。
//
// ⚠ 两趟遍历都写成**非递归**：最坏形状就是一条 10⁵ 个点的链，
//   递归必爆栈（第 30 章实测：本机 8 MB 栈，DFS 到 285380 层就段错误）。

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

static int n, m, root;
static long long MOD;
static vector<int> g[100005];
static long long w[100005];
static int fa[100005], dep[100005], siz[100005], son[100005];
static int top_[100005], dfn[100005], rnk[100005], bfsOrder[100005], cnt;

/* ---------- 线段树：区间加 + 区间求和（第 39 章那一套，这里不重讲） ---------- */
static long long sum[400005], lz[400005];
static void pull(int p) { sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % MOD; }
static void apply_(int p, int len, long long v) {
    sum[p] = (sum[p] + v % MOD * len) % MOD;
    lz[p] = (lz[p] + v) % MOD;
}
static void push(int p, int l, int r) {
    if (!lz[p]) return;
    int mid = (l + r) >> 1;
    apply_(p << 1, mid - l + 1, lz[p]);
    apply_(p << 1 | 1, r - mid, lz[p]);
    lz[p] = 0;
}
static void build(int p, int l, int r) {
    lz[p] = 0;
    if (l == r) { sum[p] = w[rnk[l]] % MOD; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pull(p);
}
static void update(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { apply_(p, r - l + 1, v); return; }
    push(p, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, v);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    push(p, l, r);
    int mid = (l + r) >> 1;
    long long s = 0;
    if (L <= mid) s += query(p << 1, l, mid, L, R);
    if (R > mid) s += query(p << 1 | 1, mid + 1, r, L, R);
    return s % MOD;
}

/* ---------- 两趟遍历（都不递归） ---------- */
static void pass1() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = root; fa[root] = 0; dep[root] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {                  // 倒着扫 BFS 序 = 从叶子往根
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;   // ★ 重儿子 = 子树最大的儿子
    }
}
static void pass2() {
    static int st[100005];
    int sp = 0;
    cnt = 0;
    top_[root] = root;
    st[sp++] = root;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        /* ⚠ 栈是后进先出：轻儿子先压、重儿子后压 ⇒ 重儿子先被弹出
           ⇒ 一条重链上的 dfn 连成一段。这就是「重儿子优先」的全部含义。 */
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; }
    }
}

/* ---------- 路径 = O(log n) 段区间 ---------- */
static void pathAdd(int x, int y, long long z) {
    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);                  // 最后一段：同一条链上的 x..y
}
static long long pathSum(int x, int y) {
    long long s = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s = (s + query(1, 1, n, dfn[top_[x]], dfn[x])) % MOD;
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return (s + query(1, 1, n, dfn[x], dfn[y])) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> root >> MOD)) return 0;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
    pass1(); pass2();
    build(1, 1, n);

    for (int i = 0; i < m; i++) {
        int op; cin >> op;
        if (op == 1) { int x, y; long long z; cin >> x >> y >> z; pathAdd(x, y, z % MOD); }
        else if (op == 2) { int x, y; cin >> x >> y; cout << pathSum(x, y) << '\n'; }
        else if (op == 3) { int x; long long z; cin >> x >> z; update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, z % MOD); }
        else { int x; cin >> x; cout << query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) << '\n'; }
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

顶格数据（n = m = 10⁵）本机实测：随机树 135 毫秒 / 链 76 毫秒 / 梳子 98 毫秒，峰值内存 17.6 MB。

★ 把它和 brute.cpp 并排看：四种操作的语义一个字都没改，换掉的只有「怎么找到那些点」。而线段树那一段是第 39 章原样搬来的，这一章一行都没重写它的逻辑。

10★★★ 一个对拍永远抓不到的 bug

wrongHeavy.cpp⚠ 重儿子挑错了

// ⚠ 故意写错的：重儿子选成「**第一个**儿子」，而不是「子树最大的儿子」
//
//     if (!son[p]) son[p] = u;          ← 正解是 if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;
//
// ★★★ 这一版**答案完全正确** —— 剖分的正确性只要求「每个点最多一个重儿子」，
//   跟挑哪个儿子毫无关系。挑错了，坏的只有**复杂度**：
//   「走一条轻边子树至少减半」这条保证没了 ⇒ 一条路径可能被拆成 O(n) 段。
//
// ⇒ 于是它是**对拍永远抓不到**的那一类 bug（第 49 章「对拍看不见的三种原因」里的第一种：
//   只影响复杂度）。⚠ 要让它现形只有两条路：**造对形状**（毛毛虫 / 特意让第一个儿子最小），
//   再**换尺子数「一条路径被拆成几段」**。见 count.cpp 那张表。
#include <bits/stdc++.h>
using namespace std;

static int n, m, root;
static long long MOD;
static vector<int> g[100005];
static long long w[100005];
static int fa[100005], dep[100005], siz[100005], son[100005];
static int top_[100005], dfn[100005], rnk[100005], bfsOrder[100005], cnt;

/* ---------- 线段树：区间加 + 区间求和（第 39 章那一套，这里不重讲） ---------- */
static long long sum[400005], lz[400005];
static void pull(int p) { sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % MOD; }
static void apply_(int p, int len, long long v) {
    sum[p] = (sum[p] + v % MOD * len) % MOD;
    lz[p] = (lz[p] + v) % MOD;
}
static void push(int p, int l, int r) {
    if (!lz[p]) return;
    int mid = (l + r) >> 1;
    apply_(p << 1, mid - l + 1, lz[p]);
    apply_(p << 1 | 1, r - mid, lz[p]);
    lz[p] = 0;
}
static void build(int p, int l, int r) {
    lz[p] = 0;
    if (l == r) { sum[p] = w[rnk[l]] % MOD; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pull(p);
}
static void update(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { apply_(p, r - l + 1, v); return; }
    push(p, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, v);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    push(p, l, r);
    int mid = (l + r) >> 1;
    long long s = 0;
    if (L <= mid) s += query(p << 1, l, mid, L, R);
    if (R > mid) s += query(p << 1 | 1, mid + 1, r, L, R);
    return s % MOD;
}

/* ---------- 两趟遍历（都不递归） ---------- */
static void pass1() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = root; fa[root] = 0; dep[root] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {                  // 倒着扫 BFS 序 = 从叶子往根
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (!son[p]) son[p] = u;                          // ⚠ 挑了第一个儿子，不是最大的
    }
}
static void pass2() {
    static int st[100005];
    int sp = 0;
    cnt = 0;
    top_[root] = root;
    st[sp++] = root;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        /* ⚠ 栈是后进先出：轻儿子先压、重儿子后压 ⇒ 重儿子先被弹出
           ⇒ 一条重链上的 dfn 连成一段。这就是「重儿子优先」的全部含义。 */
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; }
    }
}

/* ---------- 路径 = O(log n) 段区间 ---------- */
static void pathAdd(int x, int y, long long z) {
    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);                  // 最后一段：同一条链上的 x..y
}
static long long pathSum(int x, int y) {
    long long s = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s = (s + query(1, 1, n, dfn[top_[x]], dfn[x])) % MOD;
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return (s + query(1, 1, n, dfn[x], dfn[y])) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> root >> MOD)) return 0;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
    pass1(); pass2();
    build(1, 1, n);

    for (int i = 0; i < m; i++) {
        int op; cin >> op;
        if (op == 1) { int x, y; long long z; cin >> x >> y >> z; pathAdd(x, y, z % MOD); }
        else if (op == 2) { int x, y; cin >> x >> y; cout << pathSum(x, y) << '\n'; }
        else if (op == 3) { int x; long long z; cin >> x >> z; update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, z % MOD); }
        else { int x; cin >> x; cout << query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) << '\n'; }
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 它的答案完全正确 —— 1800 轮对拍，一次都抓不到

把「子树最大的儿子」改成「第一个儿子」，剖分仍然是合法的：每个点还是最多一个重儿子，链还是铺满全树，dfn 还是连续。 ⇒ 答案一个字都不会错 —— 七种形状各 300 轮，共 1800 轮，0 次不一致。

坏掉的只有那条 log 的保证：轻边不再「至少翻倍」，于是一条路径可以被拆成 O(n) 段。

★ 上一步那张表就是它的照妖镜：梳子上要拆 50 000 段，正确挑法只要 3 段 —— 差 16 666 倍。 （梳子长这样：主链上每个点先挂一片叶子，再接下一个链点 ⇒ 「第一个儿子」永远是那片叶子 ⇒ 整条主链全被判成轻边。）

⇒ 这是第 49 章说的「对拍看不见的三种原因」里的第一种： 它只影响复杂度。 而复杂度得换一把尺子数次数才看得见 —— 秒表也不太行，因为你得先造出那个形状。

11★ 对拍：五个错误版本 × 七种形状

gen.cpp生成器：七种形状

// 数据生成器（第 53 章对拍用）：`./gen <seed> [shape] [n] [m]`
//
// ★ 这一章的主旋钮不是 n，是**树的形状** —— 每个错误版本靠**不同的形状**现形：
//
//   shape 0（默认）**随机树**：i 挂到 1..i−1 里随便一个 —— 兜底
//   shape 1        **链**：i 挂到 i−1，⚠ **根随机** —— 于是链常常从中间生根，
//                  根有两个儿子，从根看它是**两条**链，不是一条。
//   shape 6        ★ **从一端生根的链**（根固定为 1）—— 这一档才是真正的「一条链」。
//                  `wrongOrder`（第二趟没让重儿子优先）在这一档上是**精确的 0**：
//                  每个点只有一个儿子，谁先谁后都一样。
//                  ⚠ 这一对（shape 1 vs 6）是这一章最该记的事：
//                    **「链」和「从根看是链」不是一回事** ——
//                    我第一版把预判写在 shape 1 上，实测 61/300 打脸，查下去才发现是根的位置。
//   shape 2        **菊花**：全挂在根上 —— 逼出「一跳就到顶」的退化路径
//   shape 3        ★ **毛毛虫**：一条主链，每个链点再挂一两个叶子
//                  —— 这一档才让「重儿子选错」和「链顶比错」同时有戏
//   shape 4        **完全二叉树**：深度 log n，轻重边交替
//
// ⚠ 生成器**顺手保证的性质**也要写下来（第 52 章那条教训）：
//   这里的 `fa[i] < i`（父亲编号一定更小）是白送的 —— 任何依赖「编号顺序 = 拓扑序」
//   的错误写法都会被它兜住。⇒ shape 5 专门**打乱编号**，把这条性质拿掉。

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int shape = (argc > 2) ? atoi(argv[2]) : 0;
    int n = (argc > 3) ? atoi(argv[3]) : ri(1, 9);
    int m = (argc > 4) ? atoi(argv[4]) : ri(1, 8);

    vector<int> par(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (shape == 1 || shape == 6) par[i] = i - 1;
        else if (shape == 2 || shape == 7) par[i] = 1;
        else if (shape == 3) par[i] = (i % 3 == 2 && i >= 5) ? i - 3 : i - 1;   // 主链 + 挂叶子
        else if (shape == 4) par[i] = i / 2;
        else par[i] = ri(1, i - 1);
    }
    /* shape 5：把编号打乱，拿掉「父亲编号更小」这条白送的性质 */
    vector<int> id(n + 1);
    for (int i = 1; i <= n; i++) id[i] = i;
    if (shape == 5) {
        for (int i = n; i > 1; i--) swap(id[i], id[ri(1, i)]);
    }

    int root = (shape == 6 || shape == 7) ? id[1] : id[ri(1, n)];   // ★ 6/7 固定根，见文件头
    long long P = ri(2, 1000);
    printf("%d %d %d %lld\n", n, m, root, P);
    for (int i = 1; i <= n; i++) printf("%d%c", ri(0, 100), i == n ? '\n' : ' ');
    for (int i = 2; i <= n; i++) printf("%d %d\n", id[i], id[par[i]]);
    for (int i = 0; i < m; i++) {
        int op = ri(1, 4);
        if (op == 1) printf("1 %d %d %d\n", id[ri(1, n)], id[ri(1, n)], ri(0, 100));
        else if (op == 2) printf("2 %d %d\n", id[ri(1, n)], id[ri(1, n)]);
        else if (op == 3) printf("3 %d %d\n", id[ri(1, n)], ri(0, 100));
        else printf("4 %d\n", id[ri(1, n)]);
    }
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

表里点名的那两个错法长这样（都只改了一处）：

wrongOrder.cpp⚠ 第二趟没让重儿子优先

// ⚠ 故意写错的：第二趟遍历**没让重儿子优先**
//
//     栈是后进先出，所以「重儿子先压、轻儿子后压」= 轻儿子先被弹出 = 重儿子**不**优先。
//
// ⇒ 一条重链上的 dfn 就**不连续**了，而整套剖分全靠那一条：
//   `[dfn[top[x]], dfn[x]]` 这段区间里会混进不属于这条链的点 ⇒ 路径答案错。
// ⚠ 注意**子树查询仍然是对的**（任何 DFS 序都白送「子树是连续区间」）——
//   所以它错的只有 op 1 / op 2 那两种。
//
// ⚠ 预判：**链**上抓不到（每个点只有一个儿子，谁优先都一样）。
//   ★ 但预判归预判，跑出来才算数 —— 见页面上那张表。
#include <bits/stdc++.h>
using namespace std;

static int n, m, root;
static long long MOD;
static vector<int> g[100005];
static long long w[100005];
static int fa[100005], dep[100005], siz[100005], son[100005];
static int top_[100005], dfn[100005], rnk[100005], bfsOrder[100005], cnt;

/* ---------- 线段树：区间加 + 区间求和（第 39 章那一套，这里不重讲） ---------- */
static long long sum[400005], lz[400005];
static void pull(int p) { sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % MOD; }
static void apply_(int p, int len, long long v) {
    sum[p] = (sum[p] + v % MOD * len) % MOD;
    lz[p] = (lz[p] + v) % MOD;
}
static void push(int p, int l, int r) {
    if (!lz[p]) return;
    int mid = (l + r) >> 1;
    apply_(p << 1, mid - l + 1, lz[p]);
    apply_(p << 1 | 1, r - mid, lz[p]);
    lz[p] = 0;
}
static void build(int p, int l, int r) {
    lz[p] = 0;
    if (l == r) { sum[p] = w[rnk[l]] % MOD; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pull(p);
}
static void update(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { apply_(p, r - l + 1, v); return; }
    push(p, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, v);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    push(p, l, r);
    int mid = (l + r) >> 1;
    long long s = 0;
    if (L <= mid) s += query(p << 1, l, mid, L, R);
    if (R > mid) s += query(p << 1 | 1, mid + 1, r, L, R);
    return s % MOD;
}

/* ---------- 两趟遍历（都不递归） ---------- */
static void pass1() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = root; fa[root] = 0; dep[root] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {                  // 倒着扫 BFS 序 = 从叶子往根
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;   // ★ 重儿子 = 子树最大的儿子
    }
}
static void pass2() {
    static int st[100005];
    int sp = 0;
    cnt = 0;
    top_[root] = root;
    st[sp++] = root;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        /* ⚠ 栈是后进先出：轻儿子先压、重儿子后压 ⇒ 重儿子先被弹出
           ⇒ 一条重链上的 dfn 连成一段。这就是「重儿子优先」的全部含义。 */
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; }        // ⚠ 重儿子先压
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
    }
}

/* ---------- 路径 = O(log n) 段区间 ---------- */
static void pathAdd(int x, int y, long long z) {
    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);                  // 最后一段：同一条链上的 x..y
}
static long long pathSum(int x, int y) {
    long long s = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s = (s + query(1, 1, n, dfn[top_[x]], dfn[x])) % MOD;
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return (s + query(1, 1, n, dfn[x], dfn[y])) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> root >> MOD)) return 0;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
    pass1(); pass2();
    build(1, 1, n);

    for (int i = 0; i < m; i++) {
        int op; cin >> op;
        if (op == 1) { int x, y; long long z; cin >> x >> y >> z; pathAdd(x, y, z % MOD); }
        else if (op == 2) { int x, y; cin >> x >> y; cout << pathSum(x, y) << '\n'; }
        else if (op == 3) { int x; long long z; cin >> x >> z; update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, z % MOD); }
        else { int x; cin >> x; cout << query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) << '\n'; }
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

wrongTop.cpp⚠ 比成了点的深度

// ⚠ 故意写错的：跳链时比的是**点**的深度，不是**链顶**的深度
//
//     if (dep[x] < dep[y]) swap(x, y);        ← 正解是 dep[top_[x]] < dep[top_[y]]
//
// ★ 为什么必须比链顶：要跳的是「链顶更深的那一个」——
//   只有它才保证「跳上去之后不会跳过头」。比点的深度会让两边交替往上错位，
//   轻则多跳几段，重则跳过 LCA 直接死循环或算进不该算的点。
//
// ⚠ 它在**菊花**上抓不到的可能性很大（每条链只有一个点，链顶就是自己）——
//   ★ 这也是要跑出来才知道的。
#include <bits/stdc++.h>
using namespace std;

static int n, m, root;
static long long MOD;
static vector<int> g[100005];
static long long w[100005];
static int fa[100005], dep[100005], siz[100005], son[100005];
static int top_[100005], dfn[100005], rnk[100005], bfsOrder[100005], cnt;

/* ---------- 线段树：区间加 + 区间求和（第 39 章那一套，这里不重讲） ---------- */
static long long sum[400005], lz[400005];
static void pull(int p) { sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % MOD; }
static void apply_(int p, int len, long long v) {
    sum[p] = (sum[p] + v % MOD * len) % MOD;
    lz[p] = (lz[p] + v) % MOD;
}
static void push(int p, int l, int r) {
    if (!lz[p]) return;
    int mid = (l + r) >> 1;
    apply_(p << 1, mid - l + 1, lz[p]);
    apply_(p << 1 | 1, r - mid, lz[p]);
    lz[p] = 0;
}
static void build(int p, int l, int r) {
    lz[p] = 0;
    if (l == r) { sum[p] = w[rnk[l]] % MOD; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pull(p);
}
static void update(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { apply_(p, r - l + 1, v); return; }
    push(p, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, v);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    push(p, l, r);
    int mid = (l + r) >> 1;
    long long s = 0;
    if (L <= mid) s += query(p << 1, l, mid, L, R);
    if (R > mid) s += query(p << 1 | 1, mid + 1, r, L, R);
    return s % MOD;
}

/* ---------- 两趟遍历（都不递归） ---------- */
static void pass1() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = root; fa[root] = 0; dep[root] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {                  // 倒着扫 BFS 序 = 从叶子往根
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;   // ★ 重儿子 = 子树最大的儿子
    }
}
static void pass2() {
    static int st[100005];
    int sp = 0;
    cnt = 0;
    top_[root] = root;
    st[sp++] = root;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        /* ⚠ 栈是后进先出：轻儿子先压、重儿子后压 ⇒ 重儿子先被弹出
           ⇒ 一条重链上的 dfn 连成一段。这就是「重儿子优先」的全部含义。 */
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; }
    }
}

/* ---------- 路径 = O(log n) 段区间 ---------- */
static void pathAdd(int x, int y, long long z) {
    while (top_[x] != top_[y]) {
        if (dep[x] < dep[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);                  // 最后一段：同一条链上的 x..y
}
static long long pathSum(int x, int y) {
    long long s = 0;
    while (top_[x] != top_[y]) {
        if (dep[x] < dep[y]) swap(x, y);                 // ⚠ 同一处错两遍
        s = (s + query(1, 1, n, dfn[top_[x]], dfn[x])) % MOD;
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return (s + query(1, 1, n, dfn[x], dfn[y])) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> root >> MOD)) return 0;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
    pass1(); pass2();
    build(1, 1, n);

    for (int i = 0; i < m; i++) {
        int op; cin >> op;
        if (op == 1) { int x, y; long long z; cin >> x >> y >> z; pathAdd(x, y, z % MOD); }
        else if (op == 2) { int x, y; cin >> x >> y; cout << pathSum(x, y) << '\n'; }
        else if (op == 3) { int x; long long z; cin >> x >> z; update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, z % MOD); }
        else { int x; cin >> x; cout << query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) << '\n'; }
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

每种形状 300 轮，和暴力答案不一致的轮数：

形状	`Order`	`Top`	`Siz`	`Last`
0 随机树	106	63	105	164
1 链（根随机）	61	41	86	172
2 菊花	81	45	126	128
3 毛毛虫	104	54	104	165
4 完全二叉树	106	74	110	163
5 打乱编号	99	54	97	160
★ 6 链（根在一端）	★ 0	★ 0	★ 0	185

★★★ 最后一行那三个 0：对暴力最坏的形状，对 bug 反而是最好的藏身处

「从一端生根的链」是暴力的最坏形状（一条路径 n 个点）。可它同时让三个错误版本一起失效，而且三个原因各不相同：

Order（第二趟没让重儿子优先）：链上每个点只有一个儿子，谁优先都一样；
Top（跳链比错了深度）：整棵树只有一条重链，top[x] == top[y] 永远成立 ⇒ 那个 while 循环一次都不进，比错也没机会发作；
Siz（子树区间多一格）：子树永远是「一直到链尾」，多出来的那一格被 min(n, …) 削回去， 和正确答案精确相等。

⇒ 「最坏数据」和「能抓 bug 的数据」是两件事，它们经常正好相反。

⚠ 而第 1 行和第 6 行的区别，只是「根在哪儿」

两行都是一条链，抓获数却完全不同（61/41/86 vs 0/0/0）—— 差别只有一个：shape 1 的根是随机挑的，链常常从中间生根，从根看它是两条链，不是一条。

★ 这是写这一章时真的栽进去过的坑：预判「链上抓不到 Order」，一跑 61/300，查下去才发现根本没造出「一条链」。 ⇒ 形状对不对，还取决于根在哪儿。 生成器里那两档都留着，就是为了记住这件事。

★ 顺带两件工具

trace.cpp 把剖分的中间结果（siz / son / top / dfn 和路径拆出来的段）打出来 —— 它存在的理由是给动画做对照：check:viz 拿它和上面两个动画的 TS 逐字节比，确保动画画的就是 fast.cpp 在做的那件事，不是「另一份长得像的实现」。

genBig.cpp 造顶格数据（四种形状），第 ④ 步那张表就是拿它量的。

trace.cpp剖分的中间结果

// 把剖分的中间结果打出来 —— 给动画做交叉验证的对照物
//
// 用法：`./trace < 输入`（输入格式和 gen.cpp 造的一样，但只读到「树」为止，操作忽略）
//
// 打三段：
//   ① 每个点的 siz / son / top / dfn
//   ② dfn 顺序（rnk）
//   ③ 对输入里每一对 (x, y)，把路径拆成的那些区间打出来
//
// ★ scripts/check-viz.mjs 拿它和 src/components/viz/hldAlgos.ts 逐字节比 ——
//   动画画的必须**就是** fast.cpp 在做的那件事，不能是「另一份长得像的实现」。

#include <bits/stdc++.h>
using namespace std;
static int n, m, root;
static vector<int> g[100005];
static int fa[100005], dep[100005], siz[100005], son[100005], top_[100005], dfn[100005], rnk[100005], bo[100005], cnt;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    long long P;
    if (!(cin >> n >> m >> root >> P)) return 0;
    for (int i = 1; i <= n; i++) { int x; cin >> x; }
    for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }

    int head = 0, tail = 0; bo[tail++] = root; fa[root] = 0; dep[root] = 1;
    while (head < tail) { int u = bo[head++]; for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bo[tail++] = v; } }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) { int u = bo[i], p = fa[u]; if (!p) continue; siz[p] += siz[u]; if (!son[p] || siz[u] > siz[son[p]]) son[p] = u; }
    { static int st[100005]; int sp = 0; cnt = 0; top_[root] = root; st[sp++] = root;
      while (sp) { int u = st[--sp]; dfn[u] = ++cnt; rnk[cnt] = u;
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; } } }

    for (int i = 1; i <= n; i++) printf("%d %d %d %d%c", siz[i], son[i], top_[i], dfn[i], i == n ? '\n' : ' ');
    for (int i = 1; i <= n; i++) printf("%d%c", rnk[i], i == n ? '\n' : ' ');

    for (int i = 0; i < m; i++) {                 // 把操作里的 (x, y) 拿来拆路径
        int op; if (!(cin >> op)) break;
        int x, y; long long z;
        if (op == 1) { cin >> x >> y >> z; }
        else if (op == 2) { cin >> x >> y; }
        else if (op == 3) { cin >> x >> z; continue; }
        else { cin >> x; continue; }
        int a = x, b = y; vector<pair<int,int>> segs;
        while (top_[a] != top_[b]) { if (dep[top_[a]] < dep[top_[b]]) swap(a, b); segs.push_back({dfn[top_[a]], dfn[a]}); a = fa[top_[a]]; }
        if (dep[a] > dep[b]) swap(a, b);
        segs.push_back({dfn[a], dfn[b]});
        printf("%d %d:", x, y);
        for (auto [l, r] : segs) printf(" %d-%d", l, r);
        printf("\n");
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

genBig.cpp顶格数据

// 顶格数据（第 53 章计时用）：`./genBig <n> <m> [shape]`
//
//   shape 0（默认）随机树
//   shape 1        ★ **链**（从一端生根）—— 暴力的最坏形状：一条路径就是 n 个点
//   shape 2        菊花
//   shape 3        ★ **梳子**：主链上每个点先挂一片叶子再接下一个链点
//                  —— 这一档是给「重儿子挑错」准备的（见 count.cpp）
//
// ⚠ 题面（洛谷 P3384）：1 <= N, M <= 10⁵，1 <= R <= N，1 <= P <= 2³⁰，
//   所有输入的数都在 int 范围内。⇒ 点权取 [0, 10⁴]，模数取一个大一点的质数。
//   ★ 上一轮（第 8、9 章）连着两次「顶格顶出题面」，这里先把范围抄下来再造。

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

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 100000;
    int m = (argc > 2) ? atoi(argv[2]) : 100000;
    int shape = (argc > 3) ? atoi(argv[3]) : 0;
    mt19937 rng(20260827u);

    printf("%d %d 1 %d\n", n, m, 1000000007);
    for (int i = 1; i <= n; i++) printf("%d%c", (int)(rng() % 10001u), i == n ? '\n' : ' ');
    for (int i = 2; i <= n; i++) {
        int p;
        if (shape == 1) p = i - 1;
        else if (shape == 2) p = 1;
        else if (shape == 3) p = (i % 2 == 0) ? max(1, i - 2) : i - 1;   // 偶数挂叶子，奇数接主链
        else p = 1 + (int)(rng() % (unsigned)(i - 1));
        printf("%d %d\n", i, p);
    }
    for (int i = 0; i < m; i++) {
        int op = 1 + (int)(rng() % 4u);
        int x = 1 + (int)(rng() % (unsigned)n), y = 1 + (int)(rng() % (unsigned)n);
        if (op == 1) printf("1 %d %d %d\n", x, y, (int)(rng() % 10001u));
        else if (op == 2) printf("2 %d %d\n", x, y);
        else if (op == 3) printf("3 %d %d\n", x, (int)(rng() % 10001u));
        else printf("4 %d\n", x);
    }
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

12边权怎么办：把边下放到点

前面四种操作都是点权。可 CSP 的树上题，一大半是边权的（「路径上所有边加 z」「问路径上边权和」）。

★ 关键一步只有一句：一条边的权，存到它「深的那一端」那个点上

每个点恰好对应它头顶那一条边 —— 根没有，所以根那一格永远是 0。于是「路径上的边」就变成了「路径上的点」。

⚠ 除了一个格子：LCA。 路径 x..y 上有 dep[x] + dep[y] − 2×dep[lca] 条边，而点比边多正好一个，多的那个就是 LCA 自己 —— 而 LCA 头顶那条边不在这条路径上。

⇒ 跳到同一条链之后，区间左端从 dfn[x] 改成 dfn[x] + 1（x 是浅的那个 = LCA）。 ★ 这就是第 52 章「点差分 vs 边差分」那条经验的延续： 点和边差一个，而差的那一个永远是 LCA。

edge.cpp边权版

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

// 边权版：把边权**下放到儿子点**，路径查询时跳过 LCA 那一格
//
// 输入格式变了：n−1 行每行 `a b c`，表示 a、b 之间有一条权为 c 的边。
// 操作只有两种（够说明问题了）：
//   1 x y z   x 到 y 路径上**每条边** += z
//   2 x y     问 x 到 y 路径上**边权**之和
//
// ============ 关键的一步只有一句 ============
//
//   **一条边 (fa[v], v) 的权，存到 v 这个点上。**
//
// 这为什么成立：每个点**恰好**对应它头顶那一条边（根没有，所以根那一格永远是 0）。
// 于是「路径上的边」就变成了「路径上的点」—— 除了一个例外：
//
// ⚠ **LCA 那一格必须去掉。** 路径 x..y 上的边有 dep[x]+dep[y]−2·dep[lca] 条，
//   而点有那么多 +1 个；多出来的那一个正是 LCA 自己，
//   而 LCA 头顶那条边**不在这条路径上**。
//   ⇒ 跳到同一条链之后，区间左端从 `dfn[x]` 改成 `dfn[x] + 1`（x 是浅的那个 = LCA）。
//   ⚠ 而且要判 `dfn[x] + 1 <= dfn[y]`：x == y 时这条路径一条边都没有。
//
// ★ 这一句就是第 52 章「点差分 vs 边差分」那条经验的延续：
//   **点和边差一个，而差的那一个永远是 LCA。**
#include <bits/stdc++.h>
using namespace std;

static int n, m, root;
static long long MOD;
static vector<int> g[100005];
static long long w[100005];
static int fa[100005], dep[100005], siz[100005], son[100005];
static int top_[100005], dfn[100005], rnk[100005], bfsOrder[100005], cnt;

/* ---------- 线段树：区间加 + 区间求和（第 39 章那一套，这里不重讲） ---------- */
static long long sum[400005], lz[400005];
static void pull(int p) { sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % MOD; }
static void apply_(int p, int len, long long v) {
    sum[p] = (sum[p] + v % MOD * len) % MOD;
    lz[p] = (lz[p] + v) % MOD;
}
static void push(int p, int l, int r) {
    if (!lz[p]) return;
    int mid = (l + r) >> 1;
    apply_(p << 1, mid - l + 1, lz[p]);
    apply_(p << 1 | 1, r - mid, lz[p]);
    lz[p] = 0;
}
static void build(int p, int l, int r) {
    lz[p] = 0;
    if (l == r) { sum[p] = w[rnk[l]] % MOD; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pull(p);
}
static void update(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { apply_(p, r - l + 1, v); return; }
    push(p, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, v);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    push(p, l, r);
    int mid = (l + r) >> 1;
    long long s = 0;
    if (L <= mid) s += query(p << 1, l, mid, L, R);
    if (R > mid) s += query(p << 1 | 1, mid + 1, r, L, R);
    return s % MOD;
}

/* ---------- 两趟遍历（都不递归） ---------- */
static void pass1() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = root; fa[root] = 0; dep[root] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {                  // 倒着扫 BFS 序 = 从叶子往根
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;   // ★ 重儿子 = 子树最大的儿子
    }
}
static void pass2() {
    static int st[100005];
    int sp = 0;
    cnt = 0;
    top_[root] = root;
    st[sp++] = root;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        /* ⚠ 栈是后进先出：轻儿子先压、重儿子后压 ⇒ 重儿子先被弹出
           ⇒ 一条重链上的 dfn 连成一段。这就是「重儿子优先」的全部含义。 */
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; }
    }
}

/* ---------- 路径 = O(log n) 段区间 ---------- */
static void pathAdd(int x, int y, long long z) {
    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);
    if (dfn[x] + 1 <= dfn[y]) update(1, 1, n, dfn[x] + 1, dfn[y], z);   // ★ +1：跳过 LCA 那一格
}
static long long pathSum(int x, int y) {
    long long s = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s = (s + query(1, 1, n, dfn[top_[x]], dfn[x])) % MOD;
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    if (dfn[x] + 1 > dfn[y]) return s;                                  // x == y：一条边都没有
    return (s + query(1, 1, n, dfn[x] + 1, dfn[y])) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> root >> MOD)) return 0;
    static int ea[100005], eb[100005]; static long long ec[100005];
    for (int i = 1; i < n; i++) { cin >> ea[i] >> eb[i] >> ec[i]; g[ea[i]].push_back(eb[i]); g[eb[i]].push_back(ea[i]); }
    pass1(); pass2();
    for (int i = 1; i <= n; i++) w[i] = 0;
    for (int i = 1; i < n; i++) {                      // ★ 边权下放到「儿子」那一端
        int child = (fa[eb[i]] == ea[i]) ? eb[i] : ea[i];
        w[child] = ec[i] % MOD;
    }
    build(1, 1, n);

    for (int i = 0; i < m; i++) {
        int op, x, y; cin >> op >> x >> y;
        if (op == 1) { long long z; cin >> z; pathAdd(x, y, z % MOD); }
        else cout << pathSum(x, y) << '\n';
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

输入

输出

路径 3 → 2 → 1 → 5 → 6 上有四条边，权是 7 + 5 + 4 + 9 = 25；每条 +10 之后是 65。

wrongEdge.cpp⚠ 忘了跳过 LCA

// ⚠ 故意写错的：边权版忘了「跳过 LCA 那一格」
//
//     query(dfn[x], dfn[y])        ← 正解是 dfn[x] + 1
//
// 于是 LCA 头顶那条边被算了进来 —— 而它**根本不在这条路径上**。
//
// ★ 它错的形状很有讲究：**LCA 是根**的时候不会错（根那一格永远是 0）。
//   ⇒ 菊花图（任意两点的 LCA 都是根）是它的**盲区**，这条要跑出来看。
#include <bits/stdc++.h>
using namespace std;

static int n, m, root;
static long long MOD;
static vector<int> g[100005];
static long long w[100005];
static int fa[100005], dep[100005], siz[100005], son[100005];
static int top_[100005], dfn[100005], rnk[100005], bfsOrder[100005], cnt;

/* ---------- 线段树：区间加 + 区间求和（第 39 章那一套，这里不重讲） ---------- */
static long long sum[400005], lz[400005];
static void pull(int p) { sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % MOD; }
static void apply_(int p, int len, long long v) {
    sum[p] = (sum[p] + v % MOD * len) % MOD;
    lz[p] = (lz[p] + v) % MOD;
}
static void push(int p, int l, int r) {
    if (!lz[p]) return;
    int mid = (l + r) >> 1;
    apply_(p << 1, mid - l + 1, lz[p]);
    apply_(p << 1 | 1, r - mid, lz[p]);
    lz[p] = 0;
}
static void build(int p, int l, int r) {
    lz[p] = 0;
    if (l == r) { sum[p] = w[rnk[l]] % MOD; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pull(p);
}
static void update(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { apply_(p, r - l + 1, v); return; }
    push(p, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, v);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    push(p, l, r);
    int mid = (l + r) >> 1;
    long long s = 0;
    if (L <= mid) s += query(p << 1, l, mid, L, R);
    if (R > mid) s += query(p << 1 | 1, mid + 1, r, L, R);
    return s % MOD;
}

/* ---------- 两趟遍历（都不递归） ---------- */
static void pass1() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = root; fa[root] = 0; dep[root] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {                  // 倒着扫 BFS 序 = 从叶子往根
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;   // ★ 重儿子 = 子树最大的儿子
    }
}
static void pass2() {
    static int st[100005];
    int sp = 0;
    cnt = 0;
    top_[root] = root;
    st[sp++] = root;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        /* ⚠ 栈是后进先出：轻儿子先压、重儿子后压 ⇒ 重儿子先被弹出
           ⇒ 一条重链上的 dfn 连成一段。这就是「重儿子优先」的全部含义。 */
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; }
    }
}

/* ---------- 路径 = O(log n) 段区间 ---------- */
static void pathAdd(int x, int y, long long z) {
    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);                                 // ⚠ 忘了 +1
}
static long long pathSum(int x, int y) {
    long long s = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s = (s + query(1, 1, n, dfn[top_[x]], dfn[x])) % MOD;
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return (s + query(1, 1, n, dfn[x], dfn[y])) % MOD;                   // ⚠ 同上
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> root >> MOD)) return 0;
    static int ea[100005], eb[100005]; static long long ec[100005];
    for (int i = 1; i < n; i++) { cin >> ea[i] >> eb[i] >> ec[i]; g[ea[i]].push_back(eb[i]); g[eb[i]].push_back(ea[i]); }
    pass1(); pass2();
    for (int i = 1; i <= n; i++) w[i] = 0;
    for (int i = 1; i < n; i++) {                      // ★ 边权下放到「儿子」那一端
        int child = (fa[eb[i]] == ea[i]) ? eb[i] : ea[i];
        w[child] = ec[i] % MOD;
    }
    build(1, 1, n);

    for (int i = 0; i < m; i++) {
        int op, x, y; cin >> op >> x >> y;
        if (op == 1) { long long z; cin >> z; pathAdd(x, y, z % MOD); }
        else cout << pathSum(x, y) << '\n';
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 「这个形状是它的盲区」—— 这句话的主语比你以为的长得多

忘了 +1，就把 LCA 头顶那条边算了进来。直觉上，菊花应该是它的盲区：任意两点的 LCA 都是根，而根那一格永远是 0，多算一格等于没多算。

实测三步，每一步都在收窄那句话的主语：

数据	`wrongEdge` 被抓（300 轮）
随机树	235
菊花，根随机	237
菊花，根在中心	214
菊花，根在中心＋只查不改＋不问自路径	★★★ 0

三次收窄各堵住一条完全不同的路：

根随机 ⇒ 根落在叶子上时，LCA 变成中心那个点，它头顶是有边的；
x == y 的自路径上一条边都没有，多算一格当场露馅；
op = 1 会把 LCA 那一格写脏，后面任何一次查询再把它读回来 —— ★ 带修改的题里，一次错误的写入会污染状态，「这一次操作看不出来」不等于「这组数据看不出来」。

⇒ 说「某个形状是盲区」之前，先把「根在哪」「问什么」「改不改」一起说完。

13回头看：第 52 章那道做不了的题

★ P3178 树上操作 —— 第 52 章故意埋的那个钩

第 52 章的题单里有一道 P3178，当时的注是：「⚠ 边改边问 —— ★ 放在这儿是为了让你亲眼看到本章这套为什么不够用」。

为什么不够用：树上差分的四个标记建立在「所有修改都做完了才开始求子树和」上。一旦「改一次、马上问一次」，差分数组还没还原，你根本读不出任何一个点的当前值。

现在可以做了。 P3178 的三种操作（单点加、子树加、根到 x 的路径求和）正好是这一章四操作里的三个 —— 把 1 x a 看成「长度为 1 的路径加」就行。

⇒ 这一章真正补上的，是「边改边问」这一整类。

14这一章没讲的

⚠ 三块，都不在 CSP-S 的常考范围里，但值得知道名字

LCT（Link-Cut Tree）：树本身会变（加边、删边）时用的。树链剖分要求树的形状从头到尾不变 —— 一旦要动树，整套 siz / son / top / dfn 全废。
长链剖分：把「子树最大」换成「深度最深」。它解决的是另一类问题（和深度有关的树上 DP），复杂度分析也完全不同。
树上莫队：离线、不带修改、但询问很怪（比如「路径上有多少种不同的颜色」）那一类。

★ 另外，这一章的线段树只写了「区间加 + 区间求和」。换成「区间取 max」「区间赋值」之类，剖分那一半一个字都不用改 —— 要改的只有第 39 章那一半。这正是分层的好处。

树链剖分：把树拆成链，让「路径」变成「区间」

1一句话问题

输入

输出

2先看清楚：难的是哪一半

3暴力：路径上一个点一个点爬

4实测：它有多慢 —— ⚠ 旋钮不是 n，是形状

5★ 关键的一步：把树拆成链

6动画一：重儿子、重链、编号

7动画二：一条路径怎么被砍成几段

8★ 为什么最多跳 log2(n) 次

9正解

10★★★ 一个对拍永远抓不到的 bug

11★ 对拍：五个错误版本 × 七种形状

12边权怎么办：把边下放到点

输入

输出

13回头看：第 52 章那道做不了的题

14这一章没讲的

15自测