最小花费

形式化题目

给定一棵 $n$ 个点的树，每条边有长度，每个城市有食物价格 $w_i$ 。有 $m$ 条旅行路线，每条从 $s$ 到 $t$ 必须沿唯一的最短路径（树上唯一路径）行走。小 R 每走一单位长度吃一单位食物，食物只能在经过的城市购买。他会选择沿路（包括终点）所有已走过城市中的最低价格买粮，求每条路线的总花费。

思路

先看一个小树基准：BFS 找到唯一的旅行路径，再逐边维护“到当前位置为止的最低粮价”并累加花费。

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:54
 */
// brute.cpp：小数据基准，BFS 找出每条旅行的唯一树路径后逐边模拟购买。
#include <bits/stdc++.h>
using namespace std;

struct Edge { int to, length; };

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

    int n, m;
    cin >> n >> m;
    vector<int> price(n + 1);
    for (int i = 1; i <= n; i++) cin >> price[i];
    vector<vector<Edge> > graph(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v, length;
        cin >> u >> v >> length;
        graph[u].push_back({v, length});
        graph[v].push_back({u, length});
    }
    while (m--) {
        int start, target;
        cin >> start >> target;
        vector<int> parent(n + 1, -1), parent_edge(n + 1);
        queue<int> q;
        q.push(start);
        parent[start] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < (int)graph[u].size(); i++) {
                int v = graph[u][i].to;
                if (parent[v] != -1) continue;
                parent[v] = u;
                parent_edge[v] = graph[u][i].length;
                q.push(v);
            }
        }
        vector<int> path;
        for (int u = target; u != 0; u = parent[u]) path.push_back(u);
        reverse(path.begin(), path.end());
        long long answer = 0;
        // 沿路径逐边模拟：每走一条边都用当前已知的最低价格买粮。
        int lowest_price = price[start];
        for (int i = 1; i < (int)path.size(); i++) {
            answer += 1LL * lowest_price * parent_edge[path[i]];
            lowest_price = min(lowest_price, price[path[i]]);
        }
        cout << answer << '\n';
    }
    return 0;
}

brute.cpp 完全按题意逐边模拟，逻辑最直观，但每次查询都要遍历整条路径，只适合小数据对拍。

核心观察

对顶点序列 $v_0, v_1, \ldots, v_k$ ，第 $i$ 条边的费用是边长乘以 $\min(w_{v_0}, \ldots, w_{v_i})$ 。价格前缀最小值只会下降，所以一条链可以压缩成若干段 (最低价格, 对应边长总和)：

一段内部价格最小值不再变化，进入这段时的最低价格决定了整段费用；
给定进入这段前的最低价格 p，二分找到第一个价格小于 p 的分段，即可在 $O(\log n)$ 内计算这段费用，并更新离开时的最低价格。

重链剖分 + 线段树

树路径的两端点方向不可交换，所以线段树为每个区间同时保存正向（左到右）和反向（右到左）两套摘要。

查询 $s \to t$ 时先求 LCA；
上行段 $s \to LCA$ 收集反向摘要，下行段 $LCA \to t$ 收集正向摘要；
相邻摘要之间的一条连接边用前一段结束时已得到的最低价格计费。

代码

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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:54
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

struct Edge {
    int to;
    int length;
};

// 一段“最低价格保持不变”的连续路程：(price, length)
struct Group {
    int price;   // 这段路程统一采用的价格
    int length;  // 这段路程的总长度
};

// 前缀统计：(length, cost) 表示前若干段的总长度与总花费
struct Prefix {
    int length;
    long long cost;
};

// 一段链（一个区间）的“价格摘要”：记录最低价格何时发生下降。
struct Summary {
    int first_price;      // 区间起点城市的价格
    int minimum_price;    // 区间内价格前缀最小值（最小值）
    int first_node;       // 区间起点的树节点
    int last_node;        // 区间终点的树节点
    vector<Group> groups; // 压缩后的 (价格, 长度) 分段列表
    vector<Prefix> prefix;// groups 的前缀长度与花费
};

// 线段树节点：同时保存正向（左到右）和反向（右到左）两套摘要。
struct SegmentNode {
    Summary forward;
    Summary backward;
};

// 查询路径时收集到的一个线段树区间：node 是节点编号，reversed 表示用反向摘要。
struct Piece {
    int node;
    bool reversed;
};

int n, m;
int price[MAXN];        // 每个城市的食物价格
int parent_node[MAXN];  // 树上的父节点
int depth[MAXN];        // 节点深度（根为 0）
int subtree_size[MAXN]; // 子树大小，用于选重儿子
int heavy_son[MAXN];    // 重儿子
int chain_top[MAXN];    // 所在重链的顶端节点
int position[MAXN];     // 节点在 dfs 序（重链优先）中的位置
int node_at[MAXN];      // position -> 节点编号
int edge_to_parent[MAXN]; // 节点到其父节点的边长
vector<Edge> graph[MAXN]; // 邻接表存树
SegmentNode segment_tree[MAXN * 4]; // 线段树
int position_count; // dfs 序分配游标

// 往 summary 的 groups 末尾追加一段 (price_value, length)，
// 若与最后一段价格相同则合并，否则新开一段。
void add_group(Summary &summary, int price_value, int length) {
    if (length == 0) return;
    if (!summary.groups.empty() && summary.groups.back().price == price_value) {
        summary.groups.back().length += length;
    } else {
        Group group = {price_value, length};
        summary.groups.push_back(group);
    }
}

// 根据 groups 重建前缀数组 prefix[i] = 前 i+1 段的总长度与总花费。
void build_prefix(Summary &summary) {
    summary.prefix.resize(summary.groups.size());
    int total_length = 0;
    long long total_cost = 0;
    for (int i = 0; i < (int)summary.groups.size(); i++) {
        total_length += summary.groups[i].length;
        total_cost += 1LL * summary.groups[i].price * summary.groups[i].length;
        summary.prefix[i] = {total_length, total_cost};
    }
}

// 合并两个相邻区间的摘要：left 在前、right 在后，
// middle_length 是连接两个区间的那条边的长度。
Summary merge_summary(const Summary &left, const Summary &right, int middle_length) {
    Summary result;
    result.first_price = left.first_price;
    result.minimum_price = min(left.minimum_price, right.minimum_price);
    result.first_node = left.first_node;
    result.last_node = right.last_node;
    result.groups = left.groups;
    // 连接边使用 left 的最小价格；left 内部的各组价格要与 right 各组取 min 后合并。
    add_group(result, left.minimum_price, middle_length);
    for (int i = 0; i < (int)right.groups.size(); i++) {
        add_group(result, min(left.minimum_price, right.groups[i].price),
                  right.groups[i].length);
    }
    build_prefix(result);
    return result;
}

// 已知进入该摘要前的最低价格 current_price，计算完整走完这段的花费。
// groups 按价格升序排列，二分找到第一个价格小于 current_price 的分段。
long long calculate_cost(const Summary &summary, int current_price) {
    int left = 0;
    int right = (int)summary.groups.size();
    while (left < right) {
        int middle = (left + right) / 2;
        if (summary.groups[middle].price >= current_price) left = middle + 1;
        else right = middle;
    }

    // 前 fixed_count 段（价格 >= current_price）改按 current_price 计费，其余段维持原价。
    int fixed_count = left;
    int fixed_length = 0;
    long long fixed_cost = 0;
    if (fixed_count > 0) {
        fixed_length = summary.prefix[fixed_count - 1].length;
        fixed_cost = summary.prefix[fixed_count - 1].cost;
    }
    long long total_cost = 0;
    if (!summary.prefix.empty()) {
        total_cost = summary.prefix.back().cost;
    }
    return 1LL * current_price * fixed_length + total_cost - fixed_cost;
}

// 迭代完成 DFS 序、子树大小、重儿子、重链划分等预处理。
void build_tree_info() {
    vector<int> order;
    vector<int> stack_nodes;
    stack_nodes.push_back(1);
    parent_node[1] = 0;
    depth[1] = 0;
    while (!stack_nodes.empty()) {
        int u = stack_nodes.back();
        stack_nodes.pop_back();
        order.push_back(u);
        for (int i = 0; i < (int)graph[u].size(); i++) {
            int v = graph[u][i].to;
            if (v == parent_node[u]) continue;
            parent_node[v] = u;
            edge_to_parent[v] = graph[u][i].length;
            depth[v] = depth[u] + 1;
            stack_nodes.push_back(v);
        }
    }
    // 逆序处理 order，得到子树大小并选出每个节点的重儿子。
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        subtree_size[u] = 1;
        heavy_son[u] = 0;
        for (int j = 0; j < (int)graph[u].size(); j++) {
            int v = graph[u][j].to;
            if (parent_node[v] != u) continue;
            subtree_size[u] += subtree_size[v];
            if (heavy_son[u] == 0 || subtree_size[v] > subtree_size[heavy_son[u]]) {
                heavy_son[u] = v;
            }
        }
    }

    // 从每条链顶端出发，沿重儿子一路给节点分配连续的 dfs 序。
    vector<pair<int, int> > chains;
    chains.push_back(make_pair(1, 1));
    while (!chains.empty()) {
        pair<int, int> current = chains.back();
        chains.pop_back();
        int u = current.first;
        int top = current.second;
        while (u != 0) {
            chain_top[u] = top;
            position[u] = ++position_count;
            node_at[position_count] = u;
            for (int i = 0; i < (int)graph[u].size(); i++) {
                int v = graph[u][i].to;
                if (parent_node[v] == u && v != heavy_son[u]) {
                    chains.push_back(make_pair(v, v));
                }
            }
            u = heavy_son[u];
        }
    }
}

// 建线段树：叶子节点是单个节点，非叶合并左右儿子的摘要。
// 相邻节点间那条边的长度由右儿子第一个节点的 edge_to_parent 给出。
void build_segment_tree(int index, int left, int right) {
    if (left == right) {
        int u = node_at[left];
        segment_tree[index].forward.first_price = price[u];
        segment_tree[index].forward.minimum_price = price[u];
        segment_tree[index].forward.first_node = u;
        segment_tree[index].forward.last_node = u;
        segment_tree[index].backward = segment_tree[index].forward;
        return;
    }
    int middle = (left + right) / 2;
    build_segment_tree(index * 2, left, middle);
    build_segment_tree(index * 2 + 1, middle + 1, right);
    int middle_length = edge_to_parent[node_at[middle + 1]];
    segment_tree[index].forward = merge_summary(segment_tree[index * 2].forward,
                                                 segment_tree[index * 2 + 1].forward,
                                                 middle_length);
    segment_tree[index].backward = merge_summary(segment_tree[index * 2 + 1].backward,
                                                  segment_tree[index * 2].backward,
                                                  middle_length);
}

// 收集查询区间 [query_left, query_right] 覆盖的线段树节点。
// reversed 为 true 时按右子树优先的顺序收集，保证返回的 pieces 沿路径顺序排列。
void collect_segments(int index, int left, int right, int query_left, int query_right,
                      bool reversed, vector<Piece> &pieces) {
    if (query_left <= left && right <= query_right) {
        Piece piece = {index, reversed};
        pieces.push_back(piece);
        return;
    }
    int middle = (left + right) / 2;
    if (!reversed) {
        if (query_left <= middle) {
            collect_segments(index * 2, left, middle, query_left, query_right, reversed, pieces);
        }
        if (query_right > middle) {
            collect_segments(index * 2 + 1, middle + 1, right, query_left, query_right,
                             reversed, pieces);
        }
    } else {
        if (query_right > middle) {
            collect_segments(index * 2 + 1, middle + 1, right, query_left, query_right,
                             reversed, pieces);
        }
        if (query_left <= middle) {
            collect_segments(index * 2, left, middle, query_left, query_right, reversed, pieces);
        }
    }
}

// 用重链跳到相同链上，深度较浅者就是 LCA。
int find_lca(int u, int v) {
    while (chain_top[u] != chain_top[v]) {
        if (depth[chain_top[u]] > depth[chain_top[v]]) u = parent_node[chain_top[u]];
        else v = parent_node[chain_top[v]];
    }
    return depth[u] < depth[v] ? u : v;
}

// 查询从 u 到 v 的最小花费。
// 上行段（u -> LCA）按反向摘要读取，下行段（LCA -> v）按正向摘要读取。
long long query_path(int u, int v) {
    int ancestor = find_lca(u, v);
    vector<Piece> pieces;
    // 收集 u 到 LCA 的上行重链段，反向读取。
    while (chain_top[u] != chain_top[ancestor]) {
        collect_segments(1, 1, n, position[chain_top[u]], position[u], true, pieces);
        u = parent_node[chain_top[u]];
    }
    collect_segments(1, 1, n, position[ancestor], position[u], true, pieces);

    // 收集 LCA 到 v 的下行重链段，正向读取；每段内部保持祖先到子孙的顺序。
    vector<vector<Piece> > down_chunks;
    while (chain_top[v] != chain_top[ancestor]) {
        vector<Piece> current_chunk;
        collect_segments(1, 1, n, position[chain_top[v]], position[v], false, current_chunk);
        down_chunks.push_back(current_chunk);
        v = parent_node[chain_top[v]];
    }
    // LCA 自身不重复计费，从 position[ancestor]+1 开始。
    if (position[ancestor] + 1 <= position[v]) {
        vector<Piece> current_chunk;
        collect_segments(1, 1, n, position[ancestor] + 1, position[v], false, current_chunk);
        down_chunks.push_back(current_chunk);
    }
    // 下行的链段按从深到浅收集，需倒序拼接到 pieces 末尾。
    for (int i = (int)down_chunks.size() - 1; i >= 0; i--) {
        for (int j = 0; j < (int)down_chunks[i].size(); j++) {
            pieces.push_back(down_chunks[i][j]);
        }
    }

    long long answer = 0;
    int current_price = 1000000007; // 走到路径起点时还没有买过食物，取足够大的初值
    int previous_node = 0;
    for (int i = 0; i < (int)pieces.size(); i++) {
        const Summary &summary = pieces[i].reversed ? segment_tree[pieces[i].node].backward
                                                     : segment_tree[pieces[i].node].forward;
        // 相邻两块摘要之间还有一条边，用上一块结束时已有的最低价格计费。
        if (previous_node != 0) {
            int edge_length = depth[previous_node] > depth[summary.first_node]
                              ? edge_to_parent[previous_node]
                              : edge_to_parent[summary.first_node];
            answer += 1LL * current_price * edge_length;
        }
        answer += calculate_cost(summary, current_price);
        // 走完这块后，手里始终保留走过的所有城市中的最低价格。
        current_price = min(current_price, summary.minimum_price);
        previous_node = summary.last_node;
    }
    return answer;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> price[i];
    for (int i = 1; i < n; i++) {
        int u, v, length;
        cin >> u >> v >> length;
        graph[u].push_back({v, length});
        graph[v].push_back({u, length});
    }
    build_tree_info();
    build_segment_tree(1, 1, n);
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << query_path(u, v) << '\n';
    }
    return 0;
}

复杂度

预处理：树剖为 $O(n)$ ，建线段树为 $O(n)$ ，总时间与空间为 $O(n\log n)$ 。
查询：一条路径拆成 $O(\log n)$ 条重链段，每段由线段树拆成 $O(\log n)$ 个摘要，每个摘要二分计算 $O(\log n)$ ，总时间 $O(\log^3 n)$ 。
空间：线段树存储每个区间的正反摘要， $O(n\log n)$ 。

总结

这类路径代价的难点是顺序不能交换。把每一段抽象为“给定当前最低价时产生多少费用”的函数，同时维护正反两个方向的摘要，重链剖分才能正确处理任意起点和终点。压缩“价格最小值不变”的连续边是本做法省掉常数因子、把每步转移到对数时间的关键。

图示解析

下面的顺序图展示一次查询从起点到终点时的摘要拼接方式：

text

1
2
3
4s -> ... -> LCA -> ... -> t
|- 上行段 s->LCA：重链段反向读取，维护已见最低价格
`- 下行段 LCA->t：各重链块倒序拼接，但每块内部仍从祖先到子孙读取
     `- 每条边的长度乘以当前已见的最低价格

每个摘要只记录“价格最低值发生改变”的边长总和。价格没有下降的连续边被合并后，无论进入价格是多少，都能用二分快速算出整段的贡献。

子任务编号	分值	$n,m\le$	特殊性质
1	10	$20$	$w_i\le 20$
2	20	$200$	无
3	40	$10^5$	一个城市至多与其它两个城市相连
4	30	$10^5$	无

目录

形式化题目

思路

核心观察

重链剖分 + 线段树

代码

复杂度

总结

图示解析