ALGORITHM NOTES阅读地图
7个主要章节
1段代码示例
8组图片与图表

先明确状态与不变量，再对照手算、证明、边界和实现。

章节速览7 节 · 展开选择

LCA 与祖先查询回答“两点在哪里会合”，子树差分把一次子树更新变成少量标记。这篇把二者接起来：给定很多条树上路径，先记下每条路径的两个端点，再从叶子向根收集标记，就能知道每条边被经过了几次。

关键问题是：为什么最近公共祖先要减二，子树里的标记和为什么恰好对应一条边？

官方题意与离线条件

191C · Fools and Roads 官方难度 1900，标签为 data structures、dfs and similar、trees。题名、标签、难度与输入范围核对于 2026-10-28，正文用自己的语言整理问题与解法。

输入一棵 n 个点的无向树，再给出 k 对端点 (a,b)。每对端点代表一次沿唯一简单路径的行程；要求输出每条边被这些行程经过的次数，保持边的输入顺序。不是统计不同端点对的种数，重复行程也要分别贡献一次。

约束为 2≤n≤100000、0≤k≤100000；端点编号在 1 到 n 之间，同一次行程允许 a=b，这时不经过任何边。树保证连通且无环，代码按这些合法输入条件实现。

若对每条路径逐边累加，链状树里一条路径就可能长达 n−1，总时间最坏为 O(nk)。本题所有行程给完才输出答案，不要求每加入一条路径就立即询问，因此可以把更新先记账，最后一次性汇总。

这次统计的是边。标记暂时存在点上，最终答案属于“这个点与父亲之间的边”。不要把中间数组直接解释成点被访问的次数，也不要把这份离线算法直接用于交错出现的在线查询。

一条路径只留下三个位置的标记

任取 1 为根。令 w=LCA(a,b)，为一次行程添加：

d[a] += 1，d[b] += 1，d[w] −= 2。

若某些位置重合，更新都累加在同一个格子。例如 a 是 b 的祖先时，w=a，a 的净变化是 −1；a=b 时，+1+1−2=0，整条零长度路径不会留下标记。

把 d 看作需要向父亲传递的“未抵消数量”。a 与 b 各送出一份，它们沿父链到 w 时汇合；w 的 −2 阻止它们继续流到 w 的父边。这个直觉帮助记忆，下面还需要用切边证明排除遗漏。

七点树中路径4到6经过4、2、1、3、6。在端点4与6各加1，在最近公共祖先1减2；子树2与子树3各留下1，汇总到根后为0。
原创教学图，只展示一条 4→6 路径。橙色边是实际经过的边，点上的 +1 与 −2 是差分标记；它们不是同一种数量。查看原图

切开一条边，证明子树和就是答案

考察非根节点 v，以及它的父边 (parent[v],v)。删去这条边后，树分为两部分，一部分恰好是 v 的子树 S。

树上的简单路径会经过这条边，当且仅当两个端点恰有一个在 S 内。一条简单路径不会来回跨过同一条边。

对刚才的一次 (a,b) 更新，S 内的差分和为：

1[a∈S] + 1[b∈S] − 2·1[w∈S]。

这里 1[条件] 在条件成立时为 1，否则为 0。因为 S 是完整的有根子树，w 在 S 内当且仅当 a、b 都在 S 内：若两点在 S 内，它们的 LCA 不会跑到 v 上方；若 w 在 S 内，作为 w 后代的两个端点也都在 S 内。

a、b 在 S 内的数量 w 是否在 S 内 子树差分和 是否经过父边
0 否 0+0−0=0 否
1 否 1+0−0=1 是
2 是 1+1−2=0 否

因此一次行程对 S 的差分和，恰好等于这次行程是否经过 v 的父边。对所有行程相加，线性叠加仍成立。定义

sum[v] = v 子树中所有初始差分标记 d 的总和，

便得到 answer[parentEdge[v]]=sum[v]。这同时证明了标记公式、累加方法以及答案与父边的对应关系。

根的子树包含整棵树，每次行程的标记总和都是零，所以最后 sum[1]=0；它是一个调试不变量，根本身没有需要输出的父边。

路径 4→5 完全位于子树 2 中，为什么边 1—2 的答案不增加？

两个端点各加 1，LCA=2 减 2。子树 2 内的总变化为 1+1−2=0；路径只走 4—2—5，不跨过子树边界。若只给 LCA 减 1，就会错误地向父边多传一份。

七个点，把标记和输出顺序分开看

使用图中的树，但把六条边按 (2,4)、(1,2)、(3,6)、(1,3)、(2,5)、(3,7) 的顺序输入。四次行程依次为 (4,5)、(4,6)、(2,7)、(3,3)。前三条分别演示同子树、跨子树、以内部节点为端点；最后一条检查零长度边界。2 并不是 7 的祖先；若另考察 2→4，LCA 才与端点 2 重合。

行程 LCA 对初始 d 的净变化 实际经过的边
4→5 2 d₄+1，d₅+1，d₂−2 4—2，2—5
4→6 1 d₄+1，d₆+1，d₁−2 4—2，2—1，1—3，3—6
2→7 1 d₂+1，d₇+1，d₁−2 2—1，1—3，3—7
3→3 3 d₃+1+1−2=0 无
节点 v初始 d[v]收集孩子后的 sum[v]写入的输入边编号
1−40根，无父边
2−122
3024
4221
5115
6113
7116

例如节点 2 收到孩子 4 的 2 和孩子 5 的 1，连同自己的 −1 得到 2；根收到两棵子树各 2，抵消自己的 −4，得到 0。最终按输入边编号输出：2 2 1 2 1 1。六个答案总和为 9，恰好等于四条路径长度 2+4+3+0。

切开节点v的父边后，子树内没有端点时贡献0，只有一个端点时贡献1，两个端点都在内时由LCA减2抵消为0；七点例按输入边序的结果是2、2、1、2、1、1。
原创证明与手算对照。上半部的三种情况针对同一条父边，不是三条不同更新规则；下半部按输入边序排列，与上表按点编号排列的顺序不同。查看原图

倍增 LCA 与非递归汇总怎样配合

预处理时，记录每个点的深度、父亲、连接父亲的输入边编号，以及二次幂级祖先 up[j][v]。up[j][v] 表示 v 向上走 2ʲ 步的位置。为了方便提升，把根的祖先都设为根；这只是 LCA 实现的边界约定，不会给根额外输出一条边。

求 LCA 时，先把深点提到相同深度；如果两点相同就返回。否则从大到小尝试共同提升，只要两个候选祖先不同便同时跳跃。最终两个点停在 LCA 的不同孩子方向，返回它们的共同父亲。每次查询 O(log n)。

遍历树时使用一个会逐步追加孩子的 order 数组，保证每个父亲早于孩子出现。这里不依赖递归 DFS，也不要求子树区间连续。反向扫描这个顺序，就保证每个孩子先于父亲汇总；这是汇总真正需要的性质。

处理非根 v 时，所有孩子已把最终值加入 d[v]，所以此刻 d[v] 就是 sum[v]。先把它写入父边答案，再执行 d[parent[v]]+=d[v]。不对根做这一步，避免根的自父亲约定引发多加一次。

完整 C++17 实现

下面先读取并保存全部行程，再调用计数函数，方便独立测试。父边使用从 0 开始的输入编号，输出位置无需重新排序。使用 long long 保存标记与计数；本题单条边答案至多 k，32 位已足够，但较宽类型也便于将每次 +1 推广为整数权重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <utility>
#include <vector>

std::vector<long long> countPaths(
    int n, const std::vector<std::pair<int, int>>& edges,
    const std::vector<std::pair<int, int>>& queries) {
    std::vector<std::vector<std::pair<int, int>>> graph(n + 1);
    for (int id = 0; id < n - 1; ++id) {
        const auto [u, v] = edges[id];
        graph[u].push_back({v, id});
        graph[v].push_back({u, id});
    }
    int levels = 1;
    while ((1LL << levels) <= n) ++levels;
    std::vector<std::vector<int>> up(levels, std::vector<int>(n + 1, 1));
    std::vector<int> parent(n + 1, 0), parentEdge(n + 1, -1);
    std::vector<int> depth(n + 1, 0), order;
    order.reserve(n);
    parent[1] = 1;
    order.push_back(1);
    for (int i = 0; i < static_cast<int>(order.size()); ++i) {
        const int v = order[i];
        for (const auto& [to, id] : graph[v]) {
            if (to == parent[v]) continue;
            parent[to] = v;
            parentEdge[to] = id;
            depth[to] = depth[v] + 1;
            up[0][to] = v;
            for (int j = 1; j < levels; ++j) {
                up[j][to] = up[j - 1][up[j - 1][to]];
            }
            order.push_back(to);
        }
    }
    const auto lca = [&](int a, int b) {
        if (depth[a] < depth[b]) std::swap(a, b);
        const int difference = depth[a] - depth[b];
        for (int j = 0; j < levels; ++j) {
            if ((difference >> j) & 1) a = up[j][a];
        }
        if (a == b) return a;
        for (int j = levels - 1; j >= 0; --j) {
            if (up[j][a] != up[j][b]) {
                a = up[j][a];
                b = up[j][b];
            }
        }
        return up[0][a];
    };
    std::vector<long long> delta(n + 1, 0), answer(n - 1, 0);
    for (const auto& [a, b] : queries) {
        const int w = lca(a, b);
        ++delta[a];
        ++delta[b];
        delta[w] -= 2;
    }
    for (int i = n - 1; i > 0; --i) {
        const int v = order[i];
        answer[parentEdge[v]] = delta[v];
        delta[parent[v]] += delta[v];
    }
    return answer;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = 0;
    std::cin >> n;
    std::vector<std::pair<int, int>> edges(n - 1);
    for (auto& [u, v] : edges) std::cin >> u >> v;
    int k = 0;
    std::cin >> k;
    std::vector<std::pair<int, int>> queries(k);
    for (auto& [a, b] : queries) std::cin >> a >> b;
    const auto answer = countPaths(n, edges, queries);
    for (int id = 0; id < n - 1; ++id) {
        if (id != 0) std::cout << ' ';
        std::cout << answer[id];
    }
    std::cout << '\n';
    return 0;
}

建树和最终汇总各 O(n)，倍增预处理 O(n log n)，k 次路径更新合计 O(k log n)，总时间 **O((n+k) log n)**。上面的完整实现保存了 k 对端点，所以额外空间为 **O(n log n+k)**。若将行程边读边更新，才可去掉 O(k) 的保存空间；这里不把未采用的优化算进当前实现。

容易混淆的边界与下一步

情况 本文行为 常见错误
k=0 每条边输出 0 假设至少有一次路径更新
a=b 三次标记在同一点抵消 把这个点误算成一条经过的边
一端是另一端祖先 祖先处净减 1 忘记端点与 LCA 会重合
多条相同路径 每次都计入，答案可为 k 对端点对去重
十万点链 迭代遍历和汇总，不占递归调用栈 深递归导致栈溢出
边输入方向或顺序改变 用 parentEdge 映射回原编号 按点编号输出 n−1 个数
要统计经过的点 需要另一套差分边界 直接把本文子树和当点答案

点计数的常见标记是端点各 +1、LCA −1、LCA 的父亲 −1；当 LCA 为根时，最后一次减法放在不汇总到树内的虚拟 0 号点，或直接跳过。它和本文的 LCA −2 服务不同的输出对象。不要把点计数公式中根的虚拟父亲，和本代码为倍增方便设置的 parent[1]=1 混用。

如果根改成另一个点，边的经过次数会改变吗？怎样检查？

不会。LCA、初始标记和哪一端被称为孩子都会变化，但切开一条无向边后“两端点是否分居两侧”的事实不变。可以重标号把另一个点映射为根 1，并保留边的输入编号，核对输出仍一致。还可检查每个答案处于 0 到 k、全部答案之和等于所有路径长度之和；这些是必要检查，不能代替完整正确性证明。

本题的收益来自“全部更新之后再统一收集”。如果需要每次更新后立即查询，或路径更新具有赋值、最大值等无法直接线性相加的语义，就要重新选择结构。可继续读重链剖分与 Water Tree，对照它怎样把路径拆成多个区间；也可以回到树算法专题，把子树、祖先、路径这三种范围放在同一条学习路线中。

本文的核验把正文 C++17 实际编译，并用逐路径 BFS 还原、删边后的连通分量参考检查小树；大规模链和星另用区间覆盖与叶端点计数核对。验证程序保留在 tests，不属于在线解法，也不把这些测试当作 Codeforces 提交通过记录。