[CSP-S 2022] 数据传输

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

把路径上的点权最短路压成 k<=3 的 min-plus 矩阵，并用重链剖分维护路径转移。

OJ: luogu

题目 ID: P8820

难度:提高+/省选-

标签:图论最短路树形结构倍增矩阵

创建: 2026-07-06 08:46

更新: 2026-10-07 12:15

前置题目

luogu P8855[POI 2002 R1] 商务旅行B 的查询复用 A 的按 LCA 拆路径步骤，从两端向 LCA 收缩合并两侧状态，再叠加重链剖分与 min-plus 矩阵

题意

给定一棵 n 个点的树。两台主机之间的树上距离不超过 k 时，可以直接传输数据。一次请求从 s 到 t，可以选择若干中转主机，要求相邻中转主机之间都能直接传输。

经过的每台主机都要付出点权 v_i，包括起点和终点。要求每次询问的最小总代价。

思路

小数据可以先求出任意两点树上距离，再把所有距离不超过 k 的点对连边，最后在这个新图上求点权最短路：

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/**
 * 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-10-01 22:33
 * update_at: 2026-10-01 22:33
 */
// brute.cpp：小数据暴力解，先 Floyd 求树上距离，再在可直接传输图上 Floyd 求最短路。
// 只适合很小的数据（n <= 50 左右），三重循环 O(n^3)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 无穷大哨兵：4e18 远大于合法答案上界，且 2*INF 不溢出（Floyd 相加会用到）。
const ll INF = 4000000000000000000LL;
const int MAXN = 55;

int n, q, K;
ll value_cost[MAXN];      // value_cost[i]：主机 i 的处理时间（点权）
ll tree_dist[MAXN][MAXN]; // tree_dist[i][j]：树上 i 到 j 的边数
ll answer_dist[MAXN][MAXN]; // answer_dist[i][j]：从 i 传到 j 的最小总代价（含两端点权）

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

    cin >> n >> q >> K;
    for (int i = 1; i <= n; i++) {
        cin >> value_cost[i];
    }

    // Floyd 求树上任意两点距离。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            tree_dist[i][j] = (i == j) ? 0 : INF;
        }
    }

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

    for (int via = 1; via <= n; via++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (tree_dist[i][j] > tree_dist[i][via] + tree_dist[via][j]) {
                    tree_dist[i][j] = tree_dist[i][via] + tree_dist[via][j];
                }
            }
        }
    }

    // 建立"距离不超过 k 即可直接传输"的新图上的点权最短路模型：
    // 走到自己代价是点权，i 直达 j 的代价是两端点权之和。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            answer_dist[i][j] = INF;
        }
        answer_dist[i][i] = value_cost[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && tree_dist[i][j] <= K) {
                answer_dist[i][j] = value_cost[i] + value_cost[j];
            }
        }
    }

    // Floyd 求最小总代价：经 via 中转时 via 的点权被加了两次，减掉一次。
    for (int via = 1; via <= n; via++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (answer_dist[i][j] > answer_dist[i][via] + answer_dist[via][j] - value_cost[via]) {
                    answer_dist[i][j] = answer_dist[i][via] + answer_dist[via][j] - value_cost[via];
                }
            }
        }
    }

    while (q--) {
        int s, t;
        cin >> s >> t;
        cout << answer_dist[s][t] << '\n';
    }

    return 0;
}

这个建模非常直接：把每台主机看成一个状态。如果当前数据在主机 u 上，那么下一步可以传到所有树上距离不超过 k 的主机 v，并额外付出 v_v 的处理时间。

因此从 s 出发时初始代价是 v_s，每条转移 u -> v 的代价是 v_v。这就是普通的最短路问题。

满数据的难点在于：不能为每次询问重新建图或跑 Dijkstra。注意 k <= 3，而一次询问只关心树上 s 到 t 的路径。最优传输路线可以理解为：沿着这条路径从两端往中间走，允许一次跨过不超过 k 条边。

于是我们维护一个长度为 k 的 DP 状态：

text

1dp[d]：当前已经处理到某个路径点，距离上一次被选作中转主机的点有 d 条边时的最小代价

因为 d 只可能是 0..k-1，每向父亲方向走过一个点，都可以用一个 k*k 的 min-plus 矩阵表示状态转移：

选择这个点作为中转点：状态回到 0，代价加上这个点的点权；
不选择这个点：距离 d 增加 1；
当 k=3 时，还要处理从路径两侧同时离路径一步、通过某个邻接点连接的特殊情况，代码中用 min_neighbor[u] 记录 u 的相邻点最小点权。

这样一段路径的转移就是若干矩阵的 min-plus 乘积。

为了快速取得从某个点向上走到链顶的转移矩阵，代码使用重链剖分：

base_matrix[u] 表示从 u 走到父亲时的一步转移；
chain_matrix[u] 表示从 u 一直走到当前重链链顶父亲的转移；
线段树按 DFS 序维护重链内部的矩阵乘积，用来处理同一条重链上的中间一段。

查询 s,t 时，分别从两端向 LCA 收缩，得到两侧 DP 状态 left_state 和 right_state。最后枚举两侧末端距离 i,j，只要 i+j <= k，两边就可以接起来，取最小代价。

代码

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/**
 * 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-10-01 22:33
 * update_at: 2026-10-01 22:33
 */
// main.cpp：k<=3 的树上点权最短路，用重链剖分维护 min-plus 转移矩阵。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 200005;
const int MAXM = 400005;
// 无穷大哨兵：4e18 远大于合法答案上界（n * max(v) <= 2e14），且 2*INF 不溢出。
const ll INF = 4000000000000000000LL;

// k <= 3 的 min-plus 转移矩阵，只用前 K 行前 K 列。
struct Matrix {
    ll a[3][3];
};

// 路径一侧的 DP 状态：a[d] 表示距离上一次选作中转主机的点 d 条边时的最小代价。
struct DpState {
    ll a[3];
};

int n, q, K;
ll val[MAXN];            // val[i]：主机 i 的处理时间（点权）
ll min_neighbor[MAXN];   // min_neighbor[u]：u 的相邻点中最小点权，k=3 时离路径一步的旁路用
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt; // 链式前向星存树
int parent_node[MAXN], depth_node[MAXN], subtree_size[MAXN], heavy_son[MAXN];
int top_node[MAXN], dfn[MAXN], rev_dfn[MAXN], dfn_cnt; // 重链剖分的链顶与 DFS 序
Matrix base_matrix[MAXN];   // base_matrix[u]：从 u 走到父亲的一步转移
Matrix chain_matrix[MAXN];  // chain_matrix[u]：从 u 走到重链链顶父亲的转移乘积
Matrix seg_tree[MAXN * 4];  // 线段树按 DFS 序维护重链内部的矩阵乘积

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

// min-plus 加法：任一加数达到哨兵量级时结果视为无穷大，避免溢出。
ll safe_add(ll x, ll y) {
    if (x >= INF / 2 || y >= INF / 2) {
        return INF;
    }
    if (x + y >= INF) {
        return INF;
    }
    return x + y;
}

// min-plus 矩阵乘法：result[i][j] = min_k (x[i][k] + y[k][j])。
Matrix multiply_matrix(const Matrix &x, const Matrix &y) {
    Matrix result;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            result.a[i][j] = INF;
        }
    }
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            for (int k = 0; k < K; k++) {
                result.a[i][j] = min(result.a[i][j], safe_add(x.a[i][k], y.a[k][j]));
            }
        }
    }
    return result;
}

// DP 状态右乘转移矩阵：result[i] = min_j (x.a[j] + y[j][i])。
DpState multiply_dp(const DpState &x, const Matrix &y) {
    DpState result;
    for (int i = 0; i < 3; i++) {
        result.a[i] = INF;
    }
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            result.a[i] = min(result.a[i], safe_add(x.a[j], y.a[j][i]));
        }
    }
    return result;
}

// 构造走到某点的一步转移：选它当中转点（状态回 0、加上点权 x）、
// 不选它（距离 +1）；k=3 时还允许经它的最小权邻居旁路（mn）。
Matrix make_transition(ll x, ll mn) {
    Matrix result;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            result.a[i][j] = INF;
        }
    }

    if (K == 1) {
        result.a[0][0] = x;
    } else if (K == 2) {
        result.a[0][0] = x;
        result.a[1][0] = x;
        result.a[0][1] = 0;
    } else {
        result.a[0][0] = x;
        result.a[1][0] = x;
        result.a[2][0] = x;
        result.a[0][1] = 0;
        result.a[1][2] = 0;
        result.a[2][2] = mn;
    }
    return result;
}

// 预处理：父节点/深度/子树大小/重儿子、链顶与 DFS 序、
// min_neighbor、base_matrix 与 chain_matrix（迭代写法避免深树爆栈）。
void build_tree_info() {
    vector<int> order;
    order.reserve(n);
    stack<int> st;
    st.push(1);
    parent_node[1] = 0;
    depth_node[1] = 1;

    // 第一遍 DFS 得到父节点、深度与遍历顺序。
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        order.push_back(u);
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            if (v == parent_node[u]) {
                continue;
            }
            parent_node[v] = u;
            depth_node[v] = depth_node[u] + 1;
            st.push(v);
        }
    }

    for (int i = 1; i <= n; i++) {
        min_neighbor[i] = INF;
    }
    for (int u = 1; u <= n; u++) {
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            min_neighbor[u] = min(min_neighbor[u], val[v]);
        }
    }

    // 逆序求子树大小与重儿子。
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        subtree_size[u] = 1;
        heavy_son[u] = 0;
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            if (v == parent_node[u]) {
                continue;
            }
            subtree_size[u] += subtree_size[v];
            if (subtree_size[v] > subtree_size[heavy_son[u]]) {
                heavy_son[u] = v;
            }
        }
    }

    // 按重链分配链顶与 DFS 序。
    stack<pair<int, int> > starts;
    starts.push(make_pair(1, 1));
    while (!starts.empty()) {
        int start = starts.top().first;
        int top = starts.top().second;
        starts.pop();

        int u = start;
        while (u != 0) {
            top_node[u] = top;
            dfn[u] = ++dfn_cnt;
            rev_dfn[dfn_cnt] = u;

            for (int e = head[u]; e != 0; e = nxt[e]) {
                int v = to[e];
                if (v == parent_node[u] || v == heavy_son[u]) {
                    continue;
                }
                starts.push(make_pair(v, v));
            }
            u = heavy_son[u];
        }
    }

    // 按 DFS 序（父先子后）构建一步转移与链上乘积。
    for (int i = 1; i <= n; i++) {
        int u = order[i - 1];
        ll parent_value = (parent_node[u] == 0) ? INF : val[parent_node[u]];
        base_matrix[u] = make_transition(parent_value, min_neighbor[u]);
        if (u == top_node[u]) {
            chain_matrix[u] = base_matrix[u];
        } else {
            chain_matrix[u] = multiply_matrix(base_matrix[u], chain_matrix[parent_node[u]]);
        }
    }
}

// 由 DFS 序区间 [l, r] 构建线段树，叶子是 base_matrix，区间值是矩阵乘积。
void build_segment_tree(int node, int l, int r) {
    if (l == r) {
        seg_tree[node] = base_matrix[rev_dfn[l]];
        return;
    }
    int mid = (l + r) / 2;
    build_segment_tree(node * 2, l, mid);
    build_segment_tree(node * 2 + 1, mid + 1, r);
    seg_tree[node] = multiply_matrix(seg_tree[node * 2 + 1], seg_tree[node * 2]);
}

// 查询 DFS 序区间 [ql, qr] 的矩阵乘积（下标大的先乘，对应先走到的父亲）。
Matrix query_segment_tree(int ql, int qr, int node, int l, int r) {
    if (ql <= l && r <= qr) {
        return seg_tree[node];
    }
    int mid = (l + r) / 2;
    if (qr <= mid) {
        return query_segment_tree(ql, qr, node * 2, l, mid);
    }
    if (ql > mid) {
        return query_segment_tree(ql, qr, node * 2 + 1, mid + 1, r);
    }
    Matrix right_part = query_segment_tree(ql, qr, node * 2 + 1, mid + 1, r);
    Matrix left_part = query_segment_tree(ql, qr, node * 2, l, mid);
    return multiply_matrix(right_part, left_part);
}

// 求 s=u 到 t=v 的最小总代价：两侧状态向 LCA 收缩后在 LCA 处合并。
ll solve_query(int u, int v) {
    if (u == v) {
        return val[u];
    }

    DpState left_state, right_state;
    for (int i = 0; i < 3; i++) {
        left_state.a[i] = right_state.a[i] = INF;
    }
    left_state.a[0] = val[u];
    right_state.a[0] = val[v];

    // 先把较深的一侧沿重链向上收缩，直到两点同链。
    while (top_node[u] != top_node[v]) {
        if (depth_node[top_node[u]] < depth_node[top_node[v]]) {
            swap(u, v);
            swap(left_state, right_state);
        }
        left_state = multiply_dp(left_state, chain_matrix[u]);
        u = parent_node[top_node[u]];
    }

    if (depth_node[u] > depth_node[v]) {
        swap(u, v);
        swap(left_state, right_state);
    }

    // 同链后 u 是 LCA；v 一侧还差 (u, v] 这一段，用线段树查询乘积。
    if (u != v) {
        Matrix middle = query_segment_tree(dfn[u] + 1, dfn[v], 1, 1, n);
        right_state = multiply_dp(right_state, middle);
    }

    // 合并两侧：两侧末端距上次中转 i、j 条边，i + j <= K 时可以直接接上。
    // i = j = 0 时 LCA 被算了两次，要减掉一次。
    ll answer = left_state.a[0] + right_state.a[0] - val[u];
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            if (i == 0 && j == 0) {
                continue;
            }
            if (i + j <= K) {
                answer = min(answer, safe_add(left_state.a[i], right_state.a[j]));
            }
        }
    }
    // k=3 时允许在 LCA 处再离路径一步，经它的最小权邻居旁路。
    if (K == 3) {
        answer = min(answer, safe_add(safe_add(left_state.a[2], right_state.a[2]), min_neighbor[u]));
    }
    return answer;
}

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

    cin >> n >> q >> K;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    build_tree_info();
    build_segment_tree(1, 1, n);

    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << solve_query(u, v) << '\n';
    }

    return 0;
}

复杂度

预处理重链剖分和线段树为 $O(n * k^3)$ ，这里 k <= 3，可以看成 $O(n)$ 。

每次询问会跳过若干条重链（至多 $O(\log n)$ 条），每跳一条做一次 $O(k^2)$ 的 DP 转移；同一条重链上的中间一段用线段树查询，每次是 $O(\log n)$ 次 $O(k^3)$ 矩阵乘法。因此单次询问复杂度为 $O(\log n * k^3)$ ， $k \leqslant 3$ 时可视为 $O(\log n)$ 。

空间复杂度为 $O(n * k^2)$ 。

总结

本题最基础的模型是“树的 k 次幂图上的点权最短路”。满分做法的关键，是发现 k <= 3 让“走过一段路径”可以压成很小的 min-plus 矩阵。

重链剖分负责把任意树上路径拆成少量连续链段，矩阵乘法负责把每段链上的选择/跳过决策合并起来。

P8820 [CSP-S 2022] 数据传输

题目背景

请勿滥用本题评测，违者可能处以封号处罚。

题目描述

小 C 正在设计计算机网络中的路由系统。

测试用的网络总共有 $n$ 台主机，依次编号为 $1 \sim n$ 。这 $n$ 台主机之间由 $n - 1$ 根网线连接，第 $i$ 条网线连接两个主机 $a_i$ 和 $b_i$ 。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率，主机 $a$ 能够直接将信息传输给主机 $b$ 当且仅当两个主机在可以通过不超过 $k$ 根网线直接或者间接的相连。

在计算机网络中，数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 $a$ 传输到主机 $b$ （ $a \neq b$ ），则其会选择出若干台用于传输的主机 $c_1 = a, c_2, \ldots, c_{m - 1}, c_m = b$ ，并按照如下规则转发：对于所有的 $1 \le i < m$ ，主机 $c_i$ 将信息直接发送给 $c_{i + 1}$ 。

每台主机处理信息都需要一定的时间，第 $i$ 台主机处理信息需要 $v_i$ 单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为 $\sum_{i = 1}^{m} v_{c_i}$ 。

现在总共有 $q$ 次数据发送请求，第 $i$ 次请求会从主机 $s_i$ 发送数据到主机 $t_i$ 。小 C 想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。

输入格式

输入的第一行包含三个正整数 $n, Q, k$ ，分别表示网络主机个数，请求个数，传输参数。数据保证 $1 \le n \le 2 \times {10}^5$ ， $1 \le Q \le 2 \times {10}^5$ ， $1 \le k \le 3$ 。

输入的第二行包含 $n$ 个正整数，第 $i$ 个正整数表示 $v_i$ ，保证 $1 \le v_i \le {10}^9$ 。

接下来 $n - 1$ 行，第 $i$ 行包含两个正整数 $a_i, b_i$ ，表示一条连接主机 $a_i, b_i$ 的网线。保证 $1 \le a_i, b_i \le n$ 。

接下来 $Q$ 行，第 $i$ 行包含两个正整数 $s_i, t_i$ ，表示一次从主机 $s_i$ 发送数据到主机 $t_i$ 的请求。保证 $1 \le s_i, t_i \le n$ ， $s_i \ne t_i$ 。

输出格式

$Q$ 行，每行一个正整数，表示第 $i$ 次请求在传输的时候至少需要花费多少单位的时间。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
9
10
117 3 3
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
4 7
5 6
1 2

输出 #1

text

说明/提示

【样例解释 #1】

对于第一组请求，由于主机 $4, 7$ 之间需要至少 $4$ 根网线才能连接，因此数据无法在两台主机之间直接传输，其至少需要一次转发；我们让其在主机 $1$ 进行一次转发，不难发现主机 $1$ 和主机 $4, 7$ 之间都只需要两根网线即可连接，且主机 $1$ 的数据处理时间仅为 $1$ ，为所有主机中最小，因此最少传输的时间为 $4 + 1 + 7 = 12$ 。

对于第三组请求，由于主机 $1, 2$ 之间只需要 $1$ 根网线就能连接，因此数据直接传输就是最优解，最少传输的时间为 $1 + 2 = 3$ 。

【样例 #2】

见附件中的 transmit/transmit2.in 与 transmit/transmit2.ans。

该样例满足测试点 $2$ 的限制。

【样例 #3】

见附件中的 transmit/transmit3.in 与 transmit/transmit3.ans。

该样例满足测试点 $3$ 的限制。

【样例 #4】

见附件中的 transmit/transmit4.in 与 transmit/transmit4.ans。

该样例满足测试点 $20$ 的限制。

【数据范围】

对于所有的测试数据，满足 $1 \le n \le 2 \times {10}^5$ ， $1 \le Q \le 2 \times {10}^5$ ， $1 \le k \le 3$ ， $1 \le a_i, b_i \le n$ ， $1 \le s_i, t_i \le n$ ， $s_i \ne t_i$ 。

测试点	$n \le$	$Q \le$	$k =$	特殊性质
$1$	$10$	$10$	$2$	是
$2$	$10$	$10$	$3$	是
$3$	$200$	$200$	$2$	是
$4 \sim 5$	$200$	$200$	$3$	是
$6 \sim 7$	$2000$	$2000$	$1$	否
$8 \sim 9$	$2000$	$2000$	$2$	否
$10 \sim 11$	$2000$	$2000$	$3$	否
$12 \sim 13$	$2 \times {10}^5$	$2 \times {10}^5$	$1$	否
$14$	$5 \times {10}^4$	$5 \times {10}^4$	$2$	是
$15 \sim 16$	${10}^5$	${10}^5$	$2$	是
$17 \sim 19$	$2 \times {10}^5$	$2 \times {10}^5$	$2$	否
$20$	$5 \times {10}^4$	$5 \times {10}^4$	$3$	是
$21 \sim 22$	${10}^5$	${10}^5$	$3$	是
$23 \sim 25$	$2 \times {10}^5$	$2 \times {10}^5$	$3$	否

特殊性质：保证 $a_i = i + 1$ ，而 $b_i$ 则从 $1, 2, \ldots, i$ 中等概率选取。

[CSP-S 2022] 数据传输

目录

题意

思路

代码

复杂度

总结