[NOIP 2015 提高组] 运输计划

GitHub跳转原题关系图 Canvas 关系图返回列表

二分答案，倍增 LCA 求路径长度，树上差分找所有超标路径的公共边并比较最大公共边权。

OJ: luogu

题目 ID: P2680

难度:提高

标签:二分答案LCA树上差分倍增

日期: 2026-07-17 02:00

形式化题目

给定一棵 $n$ 个点、 $n-1$ 条带权边的连通树，以及 $m$ 条路径 $(u_j, v_j)$ 。

操作：选择恰好一条边，把它的权值改为 $0$ 。求所有路径修改后长度的最大值的最小值。

思路

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

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/**
 * 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:59
 * update_at: 2026-08-12 22:59
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 枚举每一条边变成虫洞（边权置 0），再逐条运输计划计算改造后的路径长度，
// 记录所有计划完成时间的最大值，最后取所有选择中的最小值。
// 复杂度 O(n*m)，只适合 n、m 很小的情况。

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

const int MAXN = 55;
const int MAXM = 55;

struct EdgeInfo {
    int u, v, w;
};

struct AdjEdge {
    int to, id; // 邻接点，以及经过的边编号
};

int n, m;
EdgeInfo edges[MAXN];
vector<AdjEdge> graph_edges[MAXN];
int query_u[MAXM], query_v[MAXM];
int full_length[MAXM];      // 每条计划的原始路径长度
int path_edge_ids[MAXM][MAXN]; // path_edge_ids[i] 保存第 i 条计划经过的边编号
int path_edge_cnt[MAXM];
int parent_node[MAXN], parent_edge_id[MAXN];

// 在树上从 start 走到 target：树只有唯一一条路径，
// BFS 记录路径上每个点从哪里来、经过哪条边，再沿父链收集路径。
void find_path(int start, int target, int length_path[], int &cnt) {
    for (int i = 1; i <= n; i++) {
        parent_node[i] = -1;
        parent_edge_id[i] = 0;
    }

    queue<int> que;
    que.push(start);
    parent_node[start] = 0;

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

    // 从 target 沿父链走回 start，路径上的边倒序收集。
    cnt = 0;
    int x = target;
    while (x != start) {
        length_path[cnt] = parent_edge_id[x];
        cnt++;
        x = parent_node[x];
    }
}

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

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        graph_edges[edges[i].u].push_back({edges[i].v, i});
        graph_edges[edges[i].v].push_back({edges[i].u, i});
    }

    for (int i = 1; i <= m; i++) {
        cin >> query_u[i] >> query_v[i];
    }

    // 预处理：每条计划的路径边集合与原始长度。
    for (int i = 1; i <= m; i++) {
        find_path(query_u[i], query_v[i], path_edge_ids[i], path_edge_cnt[i]);
        full_length[i] = 0;
        for (int k = 0; k < path_edge_cnt[i]; k++) {
            full_length[i] += edges[path_edge_ids[i][k]].w;
        }
    }

    int answer = 1000000000;

    // 枚举哪一条边变成虫洞。
    for (int free_edge = 1; free_edge < n; free_edge++) {
        int worst = 0; // 这条边变成虫洞后，所有计划完成时间的最大值

        // 逐条计划计算改造后的长度：
        // 计划经过虫洞边时长度减少该边权，否则长度不变。
        for (int i = 1; i <= m; i++) {
            int length = full_length[i];
            for (int k = 0; k < path_edge_cnt[i]; k++) {
                if (path_edge_ids[i][k] == free_edge) {
                    length -= edges[free_edge].w;
                }
            }
            worst = max(worst, length);
        }

        answer = min(answer, worst);
    }

    cout << answer << '\n';

    return 0;
}

brute.cpp 对每条计划先 BFS 收集路径上的边，然后两层循环：枚举哪条边变成虫洞，逐条计划计算改造后的长度，取最大值，最后在所有选择中取最小。复杂度 $O(nm)$ ， $n, m \leqslant 300000$ 时不可行。

瓶颈有两处：一是要枚举 $n-1$ 条候选边；二是逐条计划求路径太长。解题的关键观察：

答案可以二分：时间上限 $T$ 越大越容易可行，答案是最小的可行 $T$ ，范围在 $[0, \max len_j]$ 内。
虫洞边必须是所有超标路径的公共边：固定 $T$ 后，原长度 $\leqslant T$ 的计划已经满足；原长度 $> T$ 的超标路径必须被缩短，而一条路径不经过虫洞边长度就不变，所以虫洞边必须被所有超标路径共同经过。
树上路径长度用 LCA 求： $len_j = dist[u] + dist[v] - 2 \cdot dist[lca(u,v)]$ ，倍增预处理后每条计划 $O(1)$ 拿到长度。

于是问题变成二分判定：check(T) 是否可行。

check(T) 用树上边差分一次找出所有超标路径的公共边：

\text{diff}[u] {+}{+}, \quad \text{diff}[v] {+}{+}, \quad \text{diff}[lca(u,v)] -{=}\; 2

自底向上汇总后， $\text{diff}[x]$ 恰好等于边 $(parent[x], x)$ 被多少条超标路径覆盖。覆盖数等于超标路径总数 bad_count 的边就是公共边。

差分汇总后取公共边的最大权值 best，同时记录最长超标路径的缺口 need_reduce = max(len_j - T)。可行性判据：

\text{可行} \iff \text{bad\_count} = 0 \quad \text{或} \quad \text{best} \geqslant \text{need\_reduce}

为什么这个判据是等价的：若公共边 $e$ 置 $0$ ，每条超标路径都减少 $w_e$ ，所有路径的最大长度至多变为 $\max len_j - w_e$ ，所以只要最长超标路径降到 $T$ 以内即可，即 $w_e \geqslant \max len_j - T = \text{need\_reduce}$ 。反过来，若某条边可行，它必须被所有超标路径经过（公共边），且权值满足上式。因此只比较一次最大公共边权，与"逐条路径重算"结果完全一致。

以样例验证（树边为 1-2(3), 1-6(4), 1-3(7), 3-4(6), 3-5(5)）：

计划	路径	原长度
1	3 → 6	7 + 4 = 11
2	2 → 5	3 + 7 + 5 = 15
3	4 → 5	6 + 5 = 11

取 $T = 10$ ：三条计划全部超标，但三条路径的公共边为空（计划 1 的边 {3-1, 1-6} 与计划 3 的边 {4-3, 3-5} 没有交集），不存在候选边，不可行。
取 $T = 11$ ：只有计划 2 超标，need_reduce = 15 - 11 = 4；路径 2-1-3-5 上任一边都是公共边，最大边权是边 1-3 的 7， $7 \geqslant 4$ 可行。把边 1-3 置 0 后三条计划长度为 4, 8, 11，最大值恰为 11。

代码

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194/**
 * 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:59
 * update_at: 2026-08-12 22:59
 */
// P2680 [NOIP 2015 提高组] 运输计划
// 算法：二分答案 + 倍增 LCA + 树上边差分
// 判定 limit 可行：所有原长度 > limit 的路径必须被同一条边缩短，
// 该边必须被这些超标路径全部经过，且边权 >= 最长超标路径的缺口。

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

const int MAXN = 300005;
const int MAXM = 600005;
const int LOG = 20; // 2^19 = 524288 > 3e5，倍增层数取 LOG 足够覆盖树高

struct Query {
    int u, v, lca_node;
    long long length; // 第 i 个计划的原始路径长度
};

int n, m;
int head[MAXN], to[MAXM], nxt[MAXM], edge_weight[MAXM], edge_cnt;
int depth_node[MAXN];
int up[MAXN][LOG + 1]; // up[u][j] 表示 u 的 2^j 级祖先
int parent_edge_weight[MAXN]; // parent_edge_weight[u] 表示边 (parent[u], u) 的权值
long long dist_root[MAXN];    // dist_root[u] 表示根到 u 的路径长度
int diff_count[MAXN];         // check() 中使用的边差分计数
int bfs_order[MAXN], order_cnt; // BFS 顺序，反向遍历等价于自底向上汇总
Query query_data[MAXN];

// 链式前向星加一条边。
void add_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    edge_weight[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// BFS 建树：求出深度、倍增祖先表、根到点的距离和父边权值。
// 用 BFS 而不是 DFS，避免 3e5 深度的递归爆栈。
void build_lca() {
    queue<int> que;
    que.push(1);
    depth_node[1] = 1;
    order_cnt = 0;

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        bfs_order[++order_cnt] = u;

        // 倍增转移：先跳 2^(j-1)，再跳 2^(j-1)。
        for (int j = 1; j <= LOG; j++) {
            up[u][j] = up[up[u][j - 1]][j - 1];
        }

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == up[u][0]) {
                continue;
            }
            up[v][0] = u;
            depth_node[v] = depth_node[u] + 1;
            dist_root[v] = dist_root[u] + edge_weight[i];
            parent_edge_weight[v] = edge_weight[i];
            que.push(v);
        }
    }
}

// 倍增求 lca(u, v)：先让深的点提到同一层，再同时向上跳。
int lca(int x, int y) {
    if (depth_node[x] < depth_node[y]) {
        swap(x, y);
    }

    int diff = depth_node[x] - depth_node[y];
    for (int j = LOG; j >= 0; j--) {
        if ((diff & (1 << j)) != 0) {
            x = up[x][j];
        }
    }

    if (x == y) {
        return x;
    }

    for (int j = LOG; j >= 0; j--) {
        if (up[x][j] != up[y][j]) {
            x = up[x][j];
            y = up[y][j];
        }
    }

    return up[x][0];
}

// 判断时间上限 limit 是否可行。
bool check(long long limit) {
    for (int i = 1; i <= n; i++) {
        diff_count[i] = 0;
    }

    int bad_count = 0;         // 原长度超过 limit 的超标路径条数
    long long need_reduce = 0; // 最长超标路径至少需要被缩短的量

    // 只统计超标路径。若一条超标路径不经过虫洞边，它不会变短，仍然超标。
    for (int i = 1; i <= m; i++) {
        if (query_data[i].length <= limit) {
            continue;
        }

        bad_count++;
        need_reduce = max(need_reduce, query_data[i].length - limit);

        // 边差分：路径 u -> v 的边覆盖次数整体 +1。
        // 端点处 +1、lca 处 -2，自底向上汇总后即得每条边的覆盖次数。
        int u = query_data[i].u;
        int v = query_data[i].v;
        int g = query_data[i].lca_node;
        diff_count[u]++;
        diff_count[v]++;
        diff_count[g] -= 2;
    }

    // 没有超标路径，当前 limit 已经可行。
    if (bad_count == 0) {
        return true;
    }

    long long best_common_edge = 0; // 所有超标路径公共边中的最大边权

    // 反向 BFS 序：先处理叶子，把儿子的差分值累加到父亲。
    // 汇总后 diff_count[x] 表示边 (parent[x], x) 被多少条超标路径覆盖。
    for (int i = order_cnt; i >= 1; i--) {
        int u = bfs_order[i];
        if (up[u][0] != 0 && diff_count[u] == bad_count) {
            // 这条边被所有超标路径共同经过，是虫洞的候选边。
            best_common_edge = max(best_common_edge, (long long)parent_edge_weight[u]);
        }
        if (up[u][0] != 0) {
            diff_count[up[u][0]] += diff_count[u];
        }
    }

    // 把候选公共边中权值最大的变成虫洞后，所有超标路径同时缩短该边权。
    // 可行当且仅当它不小于最长超标路径的缺口。
    return best_common_edge >= need_reduce;
}

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

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

    build_lca();

    // 读入计划，同时预处理每条计划的 lca 与原始长度。
    long long right_bound = 0;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int g = lca(u, v);
        long long len = dist_root[u] + dist_root[v] - 2LL * dist_root[g];
        query_data[i] = {u, v, g, len};
        right_bound = max(right_bound, len);
    }

    // 二分最小可行时间：答案在 [0, 最长路径长度] 内单调可行。
    long long left = 0, right = right_bound;
    while (left < right) {
        long long mid = (left + right) / 2;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    cout << left << '\n';
    return 0;
}

复杂度

预处理：BFS 建树 + 倍增表 $O(n \log n)$ ， $m$ 条计划的 LCA 与长度 $O(m \log n)$ 。
每次 check(T)：清零 + 差分 + 汇总 $O(n + m)$ 。
二分次数：答案在 $[0, \max len_j]$ 内，约 $O(\log (n \cdot 1000))$ 轮。

总时间复杂度 $O((n + m) \log n)$ ，空间 $O(n \log n + m)$ 。链形数据（测试点 13~16、20）树深达 $3 \times 10^5$ ，build_lca() 用 BFS 迭代代替 DFS，避免递归爆栈。

总结

"最小化最大值"先想到二分答案；"只改一条边"要求所有超标路径必须共享同一条边，树上边差分一次统计覆盖次数就能把公共边找出来；公共边中取最大边权与最长缺口比较，就是完整的可行性判据。本题把二分、倍增 LCA、树上边差分三个工具串成一条链：LCA 负责把路径变成公式，差分负责把"逐条路径标边"变成每条路径三个点，二分负责把枚举选边变成 $\log$ 轮判定。倍增 LCA 的预处理与查询写法取自 rbook 模板 lca-binary-lifting，见《倍增求 LCA》。

图示解析

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

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22朴素暴力（brute.cpp）
  枚举每条边置 0，逐条计划重算路径长度    O(n*m)
        |
        | 瓶颈：枚举 n-1 条边 × 每条计划，3e5 规模不可行
        v
关键观察
  1. 答案关于时间上限 T 单调可行，可以二分
  2. 虫洞边必须被所有"超标路径"共同经过（否则该路径不缩短）
  3. 树上路径长度 = dist[u] + dist[v] - 2*dist[lca]
        |
        v
二分 + 树上差分（main.cpp）
  预处理：BFS 建树，倍增表求 lca，dist 求路径长
  check(T)：
    只对长度 > T 的超标路径做边差分
      diff[u]++ , diff[v]++ , diff[lca] -= 2
    逆序汇总后 diff[x] = 边 (parent[x],x) 被覆盖次数
    覆盖次数 == 超标路径数的边 = 公共边，取最大边权 best
    可行 <=> best >= 最长超标路径的缺口 need_reduce
        |
        v
复杂度 O((n+m) log n)，空间 O(n log n)

观察要点：图中三条主线分别对应"暴力慢在哪"“观察到什么性质”“正式解如何利用这个性质”。LCA 把路径长度变成 O(1) 公式，差分把"逐条路径标边"压缩成每条路径三个点，二分把"最小化最大值"变成 $\log$ 轮判定；而"公共边"是串起一切的枢纽——差分统计出的覆盖次数，就是判断这条边能否一次救活所有超标路径的精确指标。

P2680 [NOIP 2015 提高组] 运输计划

题目背景

NOIP2015 Day2T3

题目描述

公元 $2044$ 年，人类进入了宇宙纪元。

L 国有 $n$ 个星球，还有 $n-1$ 条双向航道，每条航道建立在两个星球之间，这 $n-1$ 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 $u_i$ 号星球沿最快的宇航路径飞行到 $v_i$ 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 $j$ ，任意飞船驶过它所花费的时间为 $t_j$ ，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 $m$ 个运输计划。在虫洞建设完成后，这 $m$ 个运输计划会同时开始，所有飞船一起出发。当这 $m$ 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞，试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？

输入格式

第一行包括两个正整数 $n, m$ ，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行描述航道的建设情况，其中第 $i$ 行包含三个整数 $a_i, b_i$ 和 $t_i$ ，表示第 $i$ 条双向航道修建在 $a_i$ 与 $b_i$ 两个星球之间，任意飞船驶过它所花费的时间为 $t_i$ 。

接下来 $m$ 行描述运输计划的情况，其中第 $j$ 行包含两个正整数 $u_j$ 和 $v_j$ ，表示第 $j$ 个运输计划是从 $u_j$ 号星球飞往 $v_j$ 号星球。

输出格式

一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

所有测试数据的范围和特点如下表所示

测试点编号	$n = $	$m = $	约定
1	$100$	$1$
2	^	$100$	第 $i$ 条航道连接 $i$ 号星球与 $i + 1$ 号星球
3	^	^
4	$2000$	$1$	^
5	$1000$	$1000$	第 $i$ 条航道连接 $i$ 号星球与 $i + 1$ 号星球
6	$2000$	$2000$	^
7	$3000$	$3000$	^
8	$1000$	$1000$
9	$2000$	$2000$	^
10	$3000$	$3000$	^
11	$80000$	$1$	^
12	$100000$	^	^
13	$70000$	$70000$	第 $i$ 条航道连接 $i$ 号星球与 $i + 1$ 号星球
14	$80000$	$80000$	^
15	$90000$	$90000$	^
16	$100000$	$100000$	^
17	$80000$	$80000$
18	$90000$	$90000$	^
19	$100000$	$100000$	^
20	$300000$	$300000$	^
所有数据			$1 \le a _ i, b _ i, u _ j, v _ j \le n$ ， $0 \le t _ i \le 1000$

请注意常数因子带来的程序效率上的影响。

[NOIP 2015 提高组] 运输计划

目录

形式化题目

思路

代码

复杂度

总结

图示解析