[TJOI2015] 旅游

形式化题目

给定一棵 $n$ 个点的树，每个点有一个价格。依次执行 $q$ 次操作，每次给出 $a, b, v$ ：

沿 $a \to b$ 的路径序列 $p_1, p_2, \dots, p_k$ （ $p_1 = a, p_k = b$ ），先选一个买入城市 $p_i$ ，再选一个卖出城市 $p_j$ （ $i < j$ ，买入必须先于卖出），利润为 $price[p_j] - price[p_i]$ ，输出最大利润，为负时输出 $0$ ；
路径上所有城市的价格同时增加 $v$ 。

思路

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

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/**
 * 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:28
 * update_at: 2026-08-12 22:29
 */
// brute.cpp：小数据暴力解，对每条路径直接枚举所有（买入城市，卖出城市）点对，辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n, q;
long long price[MAXN];          // price[u] 城市 u 当前的宝石价格
vector<int> g[MAXN];            // 树的邻接表
int prev_node[MAXN];            // BFS 时记录的父链
int path[MAXN];                 // 还原出的 a -> b 路径序列
int path_len;                   // 路径长度（城市个数）

// 用 BFS 在树上求 a -> b 的路径，结果按旅行顺序放在 path[1..path_len]。
void get_path(int a, int b) {
    for (int i = 1; i <= n; i++) prev_node[i] = 0;
    queue<int> qq;
    qq.push(a);
    prev_node[a] = -1;
    while (!qq.empty()) {
        int u = qq.front();
        qq.pop();
        if (u == b) break;
        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (prev_node[v] != 0) continue;
            prev_node[v] = u;
            qq.push(v);
        }
    }
    // 从 b 沿父链回溯到 a，再反转得到 a -> b 顺序。
    int cnt = 0;
    for (int u = b; u != -1; u = prev_node[u]) {
        path[++cnt] = u;
    }
    for (int i = 1; i <= cnt / 2; i++) {
        swap(path[i], path[cnt + 1 - i]);
    }
    path_len = cnt;
}

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

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

    cin >> q;
    while (q--) {
        int a, b;
        long long v;
        cin >> a >> b >> v;
        get_path(a, b);

        // 枚举路径上的所有买卖点对：先经过的为买入城市，后经过的为卖出城市。
        long long best = 0; // 最大利润，至少为 0（不交易）
        for (int i = 1; i <= path_len; i++) {
            for (int j = i + 1; j <= path_len; j++) {
                long long profit = price[path[j]] - price[path[i]];
                if (profit > best) best = profit;
            }
        }
        cout << best << '\n';

        // ZJY 路过路径上每个城市，价格整体上涨 v。
        for (int i = 1; i <= path_len; i++) {
            price[path[i]] += v;
        }
    }

    return 0;
}

brute.cpp 每次询问用 BFS 还原出 $a \to b$ 的完整路径，然后枚举所有 $i < j$ 的买卖点对，最后把路径上每个城市的价格整体加 $v$ 。单次询问 $O(k^2)$ （ $k$ 为路径长度，最坏 $n$ ）， $q$ 次询问 $O(q n^2)$ ， $5 \times 10^4$ 的数据下不可行。

关键观察有三点：

路径是带方向的序列：买卖利润依赖"先到、后到"的顺序，只存一个最大值最小值不够——例如价格序列 [10, 1, 5]，maxv - minv = 4，但先到 10 再买、后到 5 再卖只会亏本，正确利润是 $0$ 。
四个量足以合并区间：对一段区间维护 (minv, maxv, fwd, bwd)，其中 fwd 是按段内 dfn 增序（先到左端、后到右端）的最大利润，bwd 是反序最大利润。两段按先后顺序合并时，跨段的买卖点对只有两种可能：

fwd = \max(fwd_L,\ fwd_R,\ maxv_R - minv_L)

bwd = \max(bwd_L,\ bwd_R,\ maxv_L - minv_R)

即在左段买右段卖，或在右段买左段卖。所以四元信息在合并下封闭，区间整体也能被 $O(1)$ 合并，这正是 rbook《树链剖分》文章中"路径拆分后的复合维护"一节的模型。 3. 整体加价只平移极值：区间整体加 $v$ 时，minv、maxv 各加 $v$ ，两个买卖差值不变，所以区间加可以做懒标记（线段树部分以 rbook 模板 hld 内嵌的 SegmentTree 的 pull / apply / push 结构为基底）。

于是正式解是 树链剖分 + 线段树：先把路径拆成 $O(\log n)$ 段 dfn 连续区间。注意拆出的段有方向：从 $a$ 侧取出的段 [top[a], a]，真实旅行方向是从 $a$ 走到链头，与 dfn 增序相反，取回信息时要交换 fwd / bwd（reverse_info）；从 $b$ 侧取出的段与旅行方向一致，保持正序。合并时 $a$ 侧段按取出顺序拼接、 $b$ 侧段倒序拼接，得到整条路径按 $a \to b$ 方向的四元信息，答案输出 max(0, fwd)；之后把路径上所有段做区间加 $v$ 。

下面这张表展示合并两段时四个字段的来源：

字段	左段候选	右段候选	跨段候选
`minv`	`minv_L`	`minv_R`	—
`maxv`	`maxv_L`	`maxv_R`	—
`fwd`（先左段后右段）	`fwd_L`	`fwd_R`	`maxv_R − minv_L`
`bwd`（先右段后左段）	`bwd_L`	`bwd_R`	`maxv_L − minv_R`

观察 fwd 的跨段候选：只有"在左段买、右段卖"才符合先到后到的顺序；反过来买在右段卖在左段属于 bwd。这正是"买卖有方向"在区间合并里的唯一落点——minv 与 maxv 必须分开携带，不能只存一个差值。

代码

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/**
 * 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:28
 * update_at: 2026-08-12 22:29
 */
#include <bits/stdc++.h>
using namespace std;

// 区间四元信息：
// minv 区间最小价格，maxv 区间最大价格
// fwd  按 dfn 增序（左买右卖）的最大利润，即"先到左端后到右端"
// bwd  按 dfn 减序（右买左卖）的最大利润，即"先到右端后到左端"
struct Info {
    long long minv, maxv, fwd, bwd;
};

// 按"先 first 段、后 second 段"的旅行顺序合并两段信息。
Info merge_info(const Info &a, const Info &b) {
    Info c;
    c.minv = min(a.minv, b.minv);
    c.maxv = max(a.maxv, b.maxv);
    // 正序利润三种可能：整段在 a 内、整段在 b 内、跨段（在 a 买、在 b 卖）。
    c.fwd = max(max(a.fwd, b.fwd), b.maxv - a.minv);
    // 反序利润三种可能：整段在 a 内、整段在 b 内、跨段（在 b 买、在 a 卖）。
    c.bwd = max(max(a.bwd, b.bwd), a.maxv - b.minv);
    return c;
}

// 翻转一段的旅行方向：最值不变，正序利润和反序利润交换。
Info reverse_info(const Info &a) {
    Info c;
    c.minv = a.minv;
    c.maxv = a.maxv;
    c.fwd = a.bwd;
    c.bwd = a.fwd;
    return c;
}

// 仿照 rbook 模板 hld 内嵌的 SegmentTree：pull/apply/push 结构，
// 把"区间求和"改为"四元信息"，把"区间加"改为对最值整体平移（差值不变）。
struct SegmentTree {
    int n = 0;
    vector<long long> mn, mx, fwd, bwd, lazy;

    SegmentTree(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        mn.assign(n * 4 + 5, 0);
        mx.assign(n * 4 + 5, 0);
        fwd.assign(n * 4 + 5, 0);
        bwd.assign(n * 4 + 5, 0);
        lazy.assign(n * 4 + 5, 0);
    }

    // 把两个儿子的四元信息合并回父节点。
    void pull(int p) {
        Info c = merge_info(Info{mn[p << 1], mx[p << 1], fwd[p << 1], bwd[p << 1]},
                            Info{mn[p << 1 | 1], mx[p << 1 | 1], fwd[p << 1 | 1], bwd[p << 1 | 1]});
        mn[p] = c.minv;
        mx[p] = c.maxv;
        fwd[p] = c.fwd;
        bwd[p] = c.bwd;
    }

    // 整段价格同时加 value：最值平移，买卖差值不变。
    void apply(int p, long long value) {
        mn[p] += value;
        mx[p] += value;
        lazy[p] += value;
    }

    // 下传懒标记到两个儿子。
    void push(int p) {
        if (lazy[p] == 0) return;
        apply(p << 1, lazy[p]);
        apply(p << 1 | 1, lazy[p]);
        lazy[p] = 0;
    }

    void build(int p, int l, int r, const vector<long long> &base) {
        if (l == r) {
            mn[p] = mx[p] = base[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid, base);
        build(p << 1 | 1, mid + 1, r, base);
        pull(p);
    }

    // 区间 [ql, qr] 整体加 value。
    void range_add(int ql, int qr, long long value, int p, int l, int r) {
        if (ql <= l && r <= qr) {
            apply(p, value);
            return;
        }
        push(p);
        int mid = (l + r) >> 1;
        if (ql <= mid) range_add(ql, qr, value, p << 1, l, mid);
        if (qr > mid) range_add(ql, qr, value, p << 1 | 1, mid + 1, r);
        pull(p);
    }

    // 查询区间 [ql, qr] 的四元信息，返回段内按 dfn 增序的信息。
    Info range_query(int ql, int qr, int p, int l, int r) {
        if (ql <= l && r <= qr) {
            return Info{mn[p], mx[p], fwd[p], bwd[p]};
        }
        push(p);
        int mid = (l + r) >> 1;
        bool has = false;
        Info res;
        if (ql <= mid) {
            res = range_query(ql, qr, p << 1, l, mid);
            has = true;
        }
        if (qr > mid) {
            Info t = range_query(ql, qr, p << 1 | 1, mid + 1, r);
            if (has)
                res = merge_info(res, t);
            else
                res = t;
        }
        return res;
    }
};

// 仿照 rbook 模板 hld：两次 DFS 求重儿子并分配 dfn，
// 路径操作把 u -> v 拆成 O(log n) 段连续区间交给线段树。
struct HeavyLightDecomposition {
    int n;
    int root;
    int timer = 0;
    vector<vector<int>> graph;
    vector<int> parent, depth, subtree_size, heavy_son;
    vector<int> top, dfn;
    vector<long long> value, ordered_value;
    SegmentTree seg;

    HeavyLightDecomposition(int n, int root)
        : n(n), root(root),
          graph(n + 1),
          parent(n + 1), depth(n + 1), subtree_size(n + 1),
          heavy_son(n + 1, 0), top(n + 1), dfn(n + 1),
          value(n + 1), ordered_value(n + 1),
          seg(n) {}

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

    // 第一次 DFS：求 parent、depth、subtree_size、heavy_son。
    void dfs_size(int u, int father) {
        parent[u] = father;
        depth[u] = depth[father] + 1;
        subtree_size[u] = 1;
        heavy_son[u] = 0;

        for (size_t i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            if (v == father) continue;
            dfs_size(v, u);
            subtree_size[u] += subtree_size[v];
            if (heavy_son[u] == 0 || subtree_size[v] > subtree_size[heavy_son[u]]) {
                heavy_son[u] = v;
            }
        }
    }

    // 第二次 DFS：先重儿子，让每条重链的 dfn 连续。
    void dfs_decompose(int u, int chain_top) {
        top[u] = chain_top;
        dfn[u] = ++timer;
        ordered_value[timer] = value[u];

        if (heavy_son[u] != 0) {
            dfs_decompose(heavy_son[u], chain_top);
        }

        for (size_t i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            if (v == parent[u] || v == heavy_son[u]) continue;
            dfs_decompose(v, v);
        }
    }

    void build() {
        dfs_size(root, 0);
        dfs_decompose(root, root);
        seg.build(1, 1, n, ordered_value);
    }

    // 路径 u -> v 上的所有城市价格整体加 delta。
    void path_add(int u, int v, long long delta) {
        while (top[u] != top[v]) {
            if (depth[top[u]] < depth[top[v]]) swap(u, v);
            seg.range_add(dfn[top[u]], dfn[u], delta, 1, 1, n);
            u = parent[top[u]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        seg.range_add(dfn[u], dfn[v], delta, 1, 1, n);
    }

    // 查询路径 u -> v 的四元信息（按旅行方向 u 先、v 后）。
    Info path_query(int u, int v) {
        vector<Info> left_parts;  // u 侧向上收集的段，按旅行顺序排列
        vector<Info> right_parts; // v 侧向上收集的段，按逆旅行顺序排列
        while (top[u] != top[v]) {
            if (depth[top[u]] >= depth[top[v]]) {
                // u 侧这段的旅行方向是从 u 走到链头，和 dfn 增序相反，需要反序信息。
                left_parts.push_back(reverse_info(seg.range_query(dfn[top[u]], dfn[u], 1, 1, n)));
                u = parent[top[u]];
            } else {
                // v 侧这段的旅行方向是从链头走到 v，和 dfn 增序一致。
                right_parts.push_back(seg.range_query(dfn[top[v]], dfn[v], 1, 1, n));
                v = parent[top[v]];
            }
        }
        // 最后 u、v 在同一条重链上。
        if (depth[u] >= depth[v]) {
            left_parts.push_back(reverse_info(seg.range_query(dfn[v], dfn[u], 1, 1, n)));
        } else {
            right_parts.push_back(seg.range_query(dfn[u], dfn[v], 1, 1, n));
        }
        // 按旅行顺序合并：left_parts 顺序收集，right_parts 要倒序。
        Info res;
        bool has = false;
        for (size_t i = 0; i < left_parts.size(); i++) {
            if (!has) {
                res = left_parts[i];
                has = true;
            } else {
                res = merge_info(res, left_parts[i]);
            }
        }
        for (int i = (int)right_parts.size() - 1; i >= 0; i--) {
            if (!has) {
                res = right_parts[i];
                has = true;
            } else {
                res = merge_info(res, right_parts[i]);
            }
        }
        return res;
    }
};

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

    int n;
    cin >> n;

    HeavyLightDecomposition hld(n, 1);
    for (int i = 1; i <= n; i++) {
        cin >> hld.value[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        hld.add_edge(u, v);
    }
    hld.build();

    int q;
    cin >> q;
    while (q--) {
        int a, b;
        long long v;
        cin >> a >> b >> v;
        // 答案取路径正序最大利润，亏本输出 0。
        Info res = hld.path_query(a, b);
        cout << max(0LL, res.fwd) << '\n';
        hld.path_add(a, b, v);
    }

    return 0;
}

复杂度

时间：树剖预处理 $O(n)$ ，单次路径查询或路径加 $O(\log^2 n)$ ，总 $O(n + q \log^2 n)$ 。
空间：线段树与树剖数组均为 $O(n)$ 。

总结

本题是"路径方向性统计 + 区间加"的组合：线段树节点只存最值与两个方向的最大差值，就能在合并下保持封闭；树剖负责把有方向的树上路径规约成若干连续区间，再用方向修正（reverse_info）保证合并顺序与真实旅行顺序一致。与 P3870（区间翻转懒标记）、P1438（区间加）相比，本题的关键升级是统计量必须携带方向：一旦查询信息对合并封闭且区间更新是摘要上的自同态，懒标记线段树就可以放心使用。

图示解析

这张 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）
  每次询问 BFS 求 a -> b 路径，枚举所有买卖点对 i < j
  O(k^2) 个点对，k <= n，q 次询问 O(q*n^2) 太大
        |
        | 瓶颈：路径是树上散点，且买卖必须先到后到
        v
关键观察
  路径是"有方向的序列"：
  (minv, maxv, fwd, bwd) 四元信息合并封闭
  跨段候选只有两个：b.maxv - a.minv（左买右卖）/ a.maxv - b.minv（右买左卖）
  整体加价只平移 minv、maxv，差值不变 -> 懒标记可用
        |
        v
树链剖分 + 线段树（main.cpp）
  路径 a -> b 拆成 O(log n) 段 dfn 连续区间
  a 侧段：区间 [top[a], a] 但旅行方向是 a 先到，reverse_info 交换 fwd/bwd
  b 侧段：区间 [top[b], b] 旅行方向与 dfn 增序一致，保持正序
  合并顺序：a 侧段顺序拼 + b 侧段倒序拼
  答案 = max(0, fwd)，然后路径整体区间加 v
        |
        v
复杂度 O((n + q) log^2 n)，空间 O(n)

图中四条主线分别对应"暴力慢在哪"“四元信息为什么封闭”“树剖如何拆段并修正方向”“懒标记为什么能处理路径加”。最需要记住的是 $a$ 侧段的 reverse_info：路径查询的错误几乎都来自这里——把某一段的方向搞反，合并出来的 fwd 就不再是"先到后到"的利润。

目录

形式化题目

思路

代码

复杂度

总结

图示解析