[USACO15DEC] Max Flow P

形式化题目

给出一棵 $n$ 个点的树和 $k$ 条树上路径。每条路径给出两个端点 $s_i, t_i$ ，路径经过的所有点（包括两个端点）被经过次数加一。要求输出被经过次数最多的点的次数。

思路

先看一个可以直接验证想法的朴素解：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:30
 * update_at: 2026-08-12 22:30
 */
// brute.cpp：小数据暴力解，每条路径用 BFS 找出整条路径，再沿路逐点加 1，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

int n, k;
vector<int> g[MAXN];
int pre_node[MAXN];   // BFS 中记录每个点是从哪个点走来的，用于还原路径
int count_node[MAXN]; // 每个点被经过的次数

// 把路径 start -> target 上所有点（含端点）的经过次数加 1。
void mark_path(int start, int target) {
    // BFS 找从 start 到 target 的一条路径，记录每个点的前驱。
    for (int i = 1; i <= n; i++) pre_node[i] = -1;
    queue<int> que;
    que.push(start);
    pre_node[start] = 0;

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        if (u == target) break;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (pre_node[v] == -1) {
                pre_node[v] = u;
                que.push(v);
            }
        }
    }

    // 从 target 沿前驱一路走回 start，逐点加 1。
    int x = target;
    while (x != 0) {
        count_node[x]++;
        if (x == start) break;
        x = pre_node[x];
    }
}

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

    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= k; i++) {
        int u, v;
        cin >> u >> v;
        mark_path(u, v);
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        if (answer < count_node[i]) answer = count_node[i];
    }
    cout << answer << '\n';
    return 0;
}

brute.cpp 对每条路径用 BFS 找出整条路径，再沿路逐点加 1：单条路径最坏 $O(n)$ ， $k$ 条路径总复杂度 $O(nk)$ ，无法通过 $5 \times 10^4$ 个点、 $10^5$ 条路径的数据。

关键观察是路径加一可以转成四个点的差分标记。设 $g = \text{lca}(u, v)$ ，对路径 $u \to v$ 执行：

text

1diff[u]++   diff[v]++   diff[g]--   diff[fa[g]]--

数学视角：为什么四个端点就够

一维差分是"前缀和的反向操作"：对位置 $i$ 加一，前缀和会让所有 $\geqslant i$ 的位置都加一。树上点差分把"子树和"当作"前缀和"：对点 $x$ 的标记 $+1$ ，自底向上汇总后， $x$ 的所有祖先都会加一。

于是"路径 $u \to v$ 上每个点加一"可以拆成四条"到根链"的叠加：

\text{路径 } u \to v = \text{链}(u) + \text{链}(v) - \text{链}(g) - \text{链}(fa[g])

两条链在 $g$ 处汇合： $g$ 被算两次，diff[g]-- 把它减回一次； $g$ 以上的祖先也被算两次，diff[fa[g]]-- 沿链向上恰好抵消。每条链都是单点标记，所有路径线性叠加后只做一次子树汇总即可。

以样例为例，树边为 3-4、1-5、4-2、5-4（以 1 为根：1-5-4-{2,3}），取四条有代表性的路径看差分端点：

路径	lca	差分端点（合并后净效果）	路径覆盖的点
(5,4)	5	diff[4]+1，diff[1]-1	5, 4
(3,5)	5	diff[3]+1，diff[1]-1	3, 4, 5
(4,3)	4	diff[3]+1，diff[5]-1	4, 3
(1,5)	1	diff[5]+1（根无父亲，不额外减）	1, 5

观察表中 (4,3) 一行：原始四个标记 diff[4]+1、diff[3]+1、diff[4]-1、diff[5]-1 合并成 diff[3]+1、diff[5]-1。两个正标记分别从 3、4 向上传播，lca=4 处的 -1 让 4 只被算一次，diff[5]-1 从 5 向上抵消祖先方向的两次多余贡献。

把样例 10 条路径的标记全部叠加、自底向上汇总后，每个点的真实经过次数如下：

节点	差分标记合计	子树汇总后（经过次数）
1	-6	2
2	0	0
3	+5	5
4	+4	9
5	-1	8

最大值是节点 4 的 9，与样例输出一致。观察节点 1 和节点 5：差分合计是负数，汇总后仍是正的经过次数，说明差分标记只是"中间量"，必须先完成子树汇总才是真实答案。

代码

cpp

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:30
 * update_at: 2026-08-12 22:30
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50000 + 5;
const int LOG = 16; // 2^16 = 65536 > 5*10^4，按题目规模调整

// 仿照 rbook 模板 lca-binary-lifting：倍增预处理祖先表，O(log n) 查询 LCA，
// 再叠加树上点差分，统计 k 条路径 u -> v 经过每个点的次数。
struct BinaryLCA {
    int n;
    vector<int> g[MAXN];
    int depth[MAXN];
    int up[MAXN][LOG + 1]; // up[u][j] 表示 u 的 2^j 级祖先，up[u][0] 是 u 的父亲
    int diff[MAXN];        // 树上点差分：先只记端点标记，最后自底向上汇总成真实经过次数
    int order[MAXN];       // dfs 进入顺序，倒序即"先子后父"的汇总顺序
    int order_cnt;

    void init(int n_) {
        n = n_;
        order_cnt = 0;
        for (int i = 1; i <= n; i++) {
            g[i].clear();
            depth[i] = 0;
            diff[i] = 0;
            for (int j = 0; j <= LOG; j++) up[i][j] = 0;
        }
    }

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

    // 求每个点的深度与倍增祖先表，同时记录进入顺序。
    void dfs(int u, int fa) {
        up[u][0] = fa;
        depth[u] = depth[fa] + 1;
        for (int j = 1; j <= LOG; j++) {
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
        order[++order_cnt] = u;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == fa) continue;
            dfs(v, u);
        }
    }

    void build(int root = 1) {
        depth[0] = 0;
        dfs(root, 0);
    }

    int kth_ancestor(int u, int k) const {
        for (int j = 0; j <= LOG; j++) {
            if (k & (1 << j)) u = up[u][j];
        }
        return u;
    }

    int lca(int a, int b) const {
        if (depth[a] < depth[b]) swap(a, b);

        a = kth_ancestor(a, depth[a] - depth[b]);
        if (a == b) return a;

        for (int j = LOG; j >= 0; j--) {
            if (up[a][j] != up[b][j]) {
                a = up[a][j];
                b = up[b][j];
            }
        }
        return up[a][0];
    }

    // 树上点差分：给路径 u -> v 上每个点 +1。
    // 端点 u、v 各 +1；lca 会被两条"到根"的链算两次，-1 减回一次；
    // fa[lca] -1 用来抵消 lca 以上所有祖先被算两次的多余贡献。
    void path_add(int u, int v) {
        int g = lca(u, v);
        diff[u]++;
        diff[v]++;
        diff[g]--;
        if (up[g][0] != 0) diff[up[g][0]]--;
    }

    // 自底向上汇总子树差分，返回被经过次数最多的点的次数。
    int collect_max() {
        int answer = 0;
        for (int i = order_cnt; i >= 1; i--) {
            int u = order[i];
            if (answer < diff[u]) answer = diff[u];
            if (up[u][0] != 0) diff[up[u][0]] += diff[u];
        }
        return answer;
    }
};

BinaryLCA tree; // 全局实例：内部数组较大，避免占用栈空间

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

    int n, k;
    cin >> n >> k;

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

    for (int i = 1; i <= k; i++) {
        int s, t;
        cin >> s >> t;
        tree.path_add(s, t);
    }

    cout << tree.collect_max() << '\n';
    return 0;
}

复杂度

时间：预处理 $O(n \log n)$ ，每条路径一次 LCA 查询 $O(\log n)$ ，汇总 $O(n)$ ，总 $O((n+k) \log n)$ 。
空间：倍增表与邻接表 $O(n \log n)$ 。

总结

树上点差分是"多次路径加一、最后统一统计"类问题的标准套路：用 LCA 把路径拆成两条到根的链，用四个端点标记 + 一次子树汇总代替逐条路径修改，单条路径的花费从 $O(\text{路径长})$ 降到 $O(\log n)$ 。rbook 的《倍增求 LCA》把树上差分列为 LCA 的核心应用（点差分：u、v 加，lca 和 fa[lca] 减），本解即由该模板（lca-binary-lifting）叠加差分数组改造而来。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素模拟（brute.cpp）
  每条路径 BFS 找出整条路径，沿路逐点加 1      O(n) 每条路径
        |
        | 瓶颈：k 条路径总 O(n*k)，5e4 点 1e5 路径太大
        v
关键观察
  树上点差分：路径加一 -> 四个端点标记
  diff[u]++  diff[v]++  diff[g]--  diff[fa[g]]--
  子树汇总 = 树上前缀和，把端点标记还原成真实经过次数
        |
        v
倍增 LCA + 树上点差分（main.cpp）
  预处理 up[u][j]、depth[u]，O(log n) 求 lca
  每条路径只做 4 个端点修改
  按 dfs 进入顺序倒序汇总子树，顺便取最大值
        |
        v
复杂度 O((n + k) log n)，空间 O(n log n)

图中三条主线分别对应"暴力在哪里慢"“路径加一如何退化成四个端点标记”“倍增 LCA 和子树汇总如何落地”。核心是把"整条路径修改"降级为常数个单点修改：路径可以很长，但两条到根链的重复贡献能被 -1 精确抵消，最终只剩路径本身被加一。