对答案!CSP-S 2026 真题解析:15 分暴力到 100 分正解,每档代码都给你

10 月 31 日下午，CSP-S 2026 第二轮（提高组）落幕。

这套题前两题稳、后两题硬：T1 考双指针，T2 考图论建模，T3 考状态压缩 DP，T4 考树上贪心，能力梯度清晰。

本文逐题给出：思路分析 → 各分数档题解与完整代码 → 满分标程

真题速览

通用提醒：T3、T4 多组数据，每组务必清空数组；m ≤ 10¹⁸、坐标 ≤ 10¹⁸ 到处都是，全程 long long；文件名小写、main 返回 int、禁 #pragma。

T1 能量水晶：双指针的标准开局

思路分析

观察一：统一到选中数的最大值最省。设选中 k 颗、能量和为 sum、最大值为 mx、统一到 T。只能增加 ⟹ T ≥ mx，总费用 k×T − sum。T 比 mx 大 1，每颗都多花 1 次，费用增加 k。所以目标值一定取 mx，费用 = k×mx − sum。

这一步把“选哪些 + 统一到哪”两个决策压缩成一个：集合定了，目标值就定了。

观察二：排序后存在连续区间形式的最优解。固定最大值 a[r] 和数量 k，若选了较小的 a[i] 却跳过了更靠近 r 的 a[j]（i < j ≤ r），用 a[j] 换 a[i]，费用减少 a[j] − a[i] ≥ 0。不断交换 → 存在以 r 结尾、长度 k 的连续区间最优解。

两条单调性（双指针的依据）：

• 固定右端点，左端点右移：cost(l+1, r) = cost(l, r) − (a[r] − a[l]) ≤ cost(l, r)——超预算时收缩 l 一定有效；
• 固定左端点，右端点右移：cost(l, r+1) − cost(l, r) = (r−l+1)(a[r+1] − a[r]) ≥ 0——本轮被淘汰的左端点，以后永远不会重新合法。

25 分解法：枚举所有非空子集

n ≤ 16 的测试点，二进制掩码枚举，每个子集 O(n) 统计。

注意 mx 必须初始化为 LLONG_MIN ——初始化为 0 时，选中元素全为负数会错误地把目标抬到 0。

45 分解法：O(n²) 枚举区间

枚举右端点 r，左端点 l 从 r 向左移动，增量维护费用，超预算立即 break：

for (int r = 1; r <= n; ++r) {longlong need = 0;for (int l = r; l >= 1; --l) {        need += a[r] - a[l];if (need > m) break;        ans = max(ans, r - l + 1);    }}

覆盖 n ≤ 5000 的测试点 1~9。

90 分解法：特殊条件另解（考场补充）

• 小值域（max|aᵢ| ≤ 100，测试点 6、7、10~12）：桶计数 cnt[v]，枚举目标 T ∈ [−100, 100]，按 v 从大到小贪心取 min(cnt[v], B/(T−v)) 颗，O(n + 201²)；
• 等差数列（性质 A：aᵢ = i；性质 B：公差 d）：长度 k 的费用 = d×k(k−1)/2，二分 k 即可。⚠️ 乘积可能远超 10¹⁸，用 __int128 计算后再比较，不能凭预算上限判断不溢出。

100 分解法：排序 + 前缀和 + 双指针

前缀和 O(1) 求窗口费用：cost(l,r) = a[r]×(r−l+1) − (s[r] − s[l−1])。右端点 r 从 1 扫到 n，while (cost > m) ++l 收缩——必须用 while，新增右端点可能迫使左端点连跳多次；只剩单点时费用为 0，m ≥ 0 下窗口不会删空。

满分标程

#include<algorithm>#include<iostream>#include<vector>usingnamespacestd;using ll = longlong;intmain(){    freopen("crystal.in", "r", stdin);    freopen("crystal.out", "w", stdout);// ios::sync_with_stdio(false);// cin.tie(nullptr);int n;    ll m;cin >> n >> m;vector<ll> a(n + 1), s(n + 1, 0);for (int i = 1; i <= n; ++i) cin >> a[i];    sort(a.begin() + 1, a.end());for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];auto cost = [&](int l, int r) -> ll {return a[r] * (r - l + 1LL) - (s[r] - s[l - 1]);    };int l = 1, ans = 0;for (int r = 1; r <= n; ++r) {while (cost(l, r) > m) ++l;   // 超预算时可能连续移除多个        ans = max(ans, r - l + 1);    }cout << ans << '\n';return0;}

样例 1 演算（1 2 4 8 9，m=5）：

样例 2 演算（−3 −1 2 2 7，m=8）：

r=4 时窗口 [1,4] 费用 = 2×4−0 = 8 ≤ 8 → 答案 4 ✓——负数和重复值无需任何特殊处理，公式天然兼容。

复杂度与数值范围

排序 O(n log n)，双指针部分 l 只增不减，合计 O(n)。费用保守上界 (max−min)×n ≤ 2×10¹²×5×10⁵ = 10¹⁸，long long 足够；

乘法两侧都必须已是 64 位，不能等 int 溢出后再转。

T2 地铁：“乘车免费”一句话塌缩全图

思路分析

关键观察：题目只统计步行时间，坐车本身不花时间。 同一线路上任意两个站台之间都能 0 代价互相到达——整条线路可以缩成一个点。 于是只关心「换乘」的代价：在站 v 从线路 i 换到线路 j，需要

（从 i 的站台走到站厅，再走到 j 的站台）。

算法：建一张 n 个点的线路图——对每个站 v，把它经过的线路列表 L(v)（|L(v)| ≤ d ≤ 20）两两连边，边权 t_{i,v} + t_{j,v}（同一对线路取最小值）；跑 Floyd 得全源 D[i][j]；询问枚举 i ∈ L(x)、j ∈ L(y)：

正确性：任一乘车方案 = 「进站 → 若干次换乘 → 出站」，步行时间恰好对应线路图中一条路径（方案代价 ≥ 上式）；反之线路图中任一路径可逐边还原为真实换乘序列（上式可达）。

32 分解法：小规模直接全图最短路

测试点 1~6 满足 Σk ≤ 300、q ≤ 200：把每个站台建成独立节点，同一线路的站台之间连 0 权边（免费乘车），站台与站厅连 t 权边，Floyd 一次 O((Σk)³) ≈ 3×10⁷，询问 O(1)。测试点 20、21（n = 2）两线路必有公共站，枚举公共站直接算，+8 分。

100 分解法：线路缩点 + Floyd

n ≤ 500 个点的稠密图，Floyd 三重循环 1.25×10⁸ 次在 1 秒内稳过（内层有 INF 剪枝实际更快）。

满分标程

#include<bits/stdc++.h>usingnamespacestd;using ll = longlong;staticconst ll INF = (ll)4e18;staticconstint MAXN = 505;ll D[MAXN][MAXN];intmain(){    freopen("subway.in", "r", stdin);    freopen("subway.out", "w", stdout);    ll c; int n, m, d, q;scanf("%lld %d %d %d %d", &c, &n, &m, &d, &q);    (void)c; (void)d;vector<ll> w(m + 1);for (int v = 1; v <= m; ++v) scanf("%lld", &w[v]);vector<vector<pair<int,int>>> L(m + 1);      // 每站: (线路, t)for (int i = 0; i < n; ++i) {int k; scanf("%d", &k);for (int j = 0; j < k; ++j) {int a, t; scanf("%d %d", &a, &t);            L[a].push_back({i, t});        }    }for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j)            D[i][j] = (i == j ? 0 : INF);for (int v = 1; v <= m; ++v) {               // 同站线路两两连边constauto &vec = L[v];int sz = (int)vec.size();for (int a = 0; a < sz; ++a)for (int b = a + 1; b < sz; ++b) {int i = vec[a].first, j = vec[b].first;                ll val = (ll)vec[a].second + vec[b].second;if (val < D[i][j]) { D[i][j] = val; D[j][i] = val; }            }    }for (int k = 0; k < n; ++k)                  // Floyd 全源for (int i = 0; i < n; ++i) {            ll dik = D[i][k];if (dik == INF) continue;            // 剪枝for (int j = 0; j < n; ++j) {                ll nd = dik + D[k][j];if (nd < D[i][j]) D[i][j] = nd;            }        }while (q--) {int x, y; scanf("%d %d", &x, &y);        ll best = INF;for (constauto &p : L[x]) {            ll ti = p.second;const ll *row = D[p.first];for (constauto &s : L[y]) {                ll v = ti + row[s.first] + (ll)s.second;if (v < best) best = v;            }        }printf("%lld\n", w[x] + w[y] + best);    }return0;}

样例 2 演算：c(L1,L2) = 5+6 = 11（站 2），c(L2,L3) = 1+2 = 3（站 3），c(L1,L3) = 200（站 5）；D(L1,L3) = min(200, 11+3) = 14；询问 (1,6)：4 + 14 + 7 = 25，答案 = 8+2+25 = 35 ✓；询问 (2,3)：最优 t₂,₂ + D(2,2) + t₂,₃ = 6+0+1 = 7，答案 = 3+6+7 = 16 ✓

复杂度与坑点

时间 O(Σg_v² + n³ + qd²)，其中 Σg² ≤ d·Σk ≤ 10⁷；空间 O(m + Σk + n²)。

• 同一线路必须缩成一个点，站台逐个建点会导致边数爆炸；
• 换乘代价是两段之和t_{i,v} + t_{j,v}，别只算一段；
• 特殊性质一句话：B（所有 t = T）时答案 = w_x + w_y + 2T×(最少乘线数)，线路图 BFS 即可；A（kᵢ ≤ 2）时线路退化为边——满分算法对两者通用。

T3 迁徙：“只存前三项”的神来之笔

思路分析

共同观察一：最短路径一定向右走。固定 s < v，若路径发生转向，存在连续三岛 a、b、c（b 坐标最大或最小），由三角不等式 |x_a − x_c| ≤ max(|x_a − x_b|, |x_b − x_c|) ≤ d，可把 a→b→c 改为 a→c，路径变短，矛盾。绕路的重复岛也可删去。 于是只需统计严格向右的路径。

共同观察二：BFS 的每一层都是连续区间。预处理 r[i] = 从 i 一步能到达的最右岛屿（双指针 O(n)，且 r 单调不降）。固定起点 s：第 0 层 {s}；若当前层为 [L, R]，下一层就是

（当前层所有点能到的最右位置是 r[R]，而 R 右侧、不超过 r[R] 的每个点都能直接由 R 到达）。若 r[R] = R，后面无法继续，结束。

40 分解法：按层转移，前缀和计数

固定起点 s，cnt[v] = s 到 v 的最短路径条数。下一层的终点 v，能作为它最后一步前驱的岛恰好是 [max(L, l[v]), R]，因此：

对当前层做前缀和即 O(1) 求一个点。本题只关心是否恰好为 2——每个 cnt 只保存 0,1,2,3（3 = 至少三条）：

cnt 可以截断，前缀和不能提前截断：前缀和存截断后各项之和，区间相减后再对结果截断。若截断和 ≥ 3 则真实 ≥ 3；若 ≤ 2 则每项都没被截断、真实和 = 截断和。两种情况都能正确判断"恰好 = 2"。 枚举所有起点、只统计右侧终点，答案不重不漏。每起点每岛处理常数次 → O(n²)，覆盖测试点 1~10。

#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;intmain(){    freopen("migrate.in", "r", stdin);    freopen("migrate.out", "w", stdout);int c, t;scanf("%d %d", &c, &t);while (t--) {int n; ll d;scanf("%d %lld", &n, &d);vector<ll> x(n + 1);for (int i = 1; i <= n; i++) scanf("%lld", &x[i]);vector<int> r(n + 1), l(n + 1);for (int i = 1, j = 1; i <= n; i++) {if (j < i) j = i;while (j < n && x[j + 1] - x[i] <= d) j++;            r[i] = j;        }for (int i = n, j = n; i >= 1; i--) {if (j > i) j = i;while (j > 1 && x[i] - x[j - 1] <= d) j--;            l[i] = j;        }        ll ans = 0;vector<ll> cnt(n + 1), pre(n + 1);for (int s = 1; s <= n; s++) {            fill(cnt.begin(), cnt.end(), 0);            cnt[s] = 1;int L = s, R = s;while (R < n && r[R] > R) {int nR = r[R];                pre[L - 1] = 0;for (int v = L; v <= R; v++) pre[v] = pre[v - 1] + cnt[v];for (int v = R + 1; v <= nR; v++) {int lo = max(L, l[v]);                    ll c2 = pre[R] - pre[lo - 1];                    cnt[v] = min(c2, 3LL);      // 截断：3 表示至少三条if (cnt[v] == 2) ans++;                }                L = R + 1; R = nR;            }        }printf("%lld\n", ans);    }return0;}

样例 1 演算（1 2 3 4，d=2）：s=1 时层 0 [1,1] → 层 1 [2,3] cnt=(1,1) → 层 2 [4,4]：cnt[4] = cnt[2]+cnt[3] = 2 → 贡献 1 ✓（s=2 时 2→4 直达、最短唯一，无贡献）。

特殊性质补充

• 性质 A（等差数列，测试点 11、12）：设公差 g，贪心每步恰跳 q = ⌊d/g⌋ 个下标，可推出答案为 max(0, n − 2q + 1)（q ≥ 2 时）；
• 性质 B（枢纽岛，测试点 13、14）：任意两点 dist ≤ 2，答案 = #{(u,v) : x_v − x_u > d 且区间 [x_v−d, x_u+d] 内恰有 2 座岛}，排序 + 二分 O(n log n)。

100 分解法：只保留三个路径终点

部分分的问题：每个起点都重新处理了许多相同的后续情况。要合并计算，先回答——决定后续答案，真的需要保存整层的方案数吗？

1. 把路径看成带重复的终点列表。考虑某一起点的当前 BFS 层，每条最短路径贡献一次它的终点编号。例如到达岛 7 有两条、岛 6 有一条，列表为 7, 7, 6, …。按编号从大到小只保留前三项，记为 a ≥ b ≥ c（不足记“空”）。这里的重复非常重要：a = b 表示有两条不同路径到达同一座最右岛屿。

2. 为什么前三项就够了？下一层的岛 v（v > a）能接在终点 u 的路径后面 ⟺ **v ≤ r[u]**。r 单调不降 → 终点编号越大延伸越远：

• 至少一条路径到 v ⟺ v ≤ r[a]；
• 至少两条 ⟺ b 存在且 v ≤ r[b]；
• 至少三条 ⟺ c 存在且 v ≤ r[c]。 第四条及之后的路径不改变这三个判断（它的终点 ≤ c，能延伸到的 v 第三条也能延伸到）。

3. 下一层前三项的转移公式。从终点 a 的路径出发，新终点为 r[a], r[a]−1, …, a+1；从 b、c 出发类似，记 q_b = max(a, r[b])（b 空时 q_b = a）、q_c 同理。下一层前三项（记 A = r[a]）：

（“第一条一条、第二条两条”的候选 q_b − 1 不超过 min(A−1, q_b)，不用单写。）

4. 恰好两条的区间。下一层中恰好有两条最短路径的终点构成区间 (q_c, q_b]，贡献直接是 q_b − q_c：

q_c < v ≤ q_b 时：v ≤ q_b ⟹ 能接至少两条；v > q_c ⟹ 接不了第三条（q_c 已用 a 兜底表示“空”）→ 恰好两条。✓

5. 状态数是常数！由转移公式：只要第二项存在就有 B ≥ A−1，只要第三项存在就有 C ≥ A−2。于是 b 相对 A 的偏移只能是 {0, 1, 空}，c 只能是 {0, 1, 2, 空}，共 8 种状态：

DP 定义：f[a][k] = 当前层状态为（终点 a、偏移 k）时，所有后续层中恰好两条路径的终点数：

因 A = r[a] > a，按 a 从大到小计算即可。每个起点的初始状态都是（s, 空, 空）= 状态 7，所以：

样例走一遍（1 2 3 4，d=2，起点 1）：

• 第 0 层状态 (1, 空, 空)，第 1 层路径终点 3, 2 → 状态 (3, 2, 空)；
• 处理 a=3（状态偏移 b=2, c=空）：q_b = max(3, r[2]=4) = 4，q_c = 3，A = r[3] = 4 → 下一层前三项 (4, 4, 空)，贡献 q_b − q_c = 1（终点 4 恰好两条：1→2→4 与 1→3→4）✓
• f[1][7] = 0 + 1 = 1 ✓

满分标程

#include<bits/stdc++.h>usingnamespacestd;using ll = longlong;constint EMPTY = 3;                              // 3 表示空，其余为与最右终点 a 的编号差constint db[8] = {0, 0, 0, 0, 1, 1, 1, 3};constint dc[8] = {0, 1, 2, 3, 1, 2, 3, 3};voidsolve(){int n; ll d;cin >> n >> d;vector<ll> x(n + 1);for (int i = 1; i <= n; ++i) cin >> x[i];vector<int> r(n + 1);                         // r[i]: 从 i 一步能到的最右岛for (int i = 1, j = 1; i <= n; ++i) {        j = max(j, i);while (j < n && x[j + 1] - x[i] <= d) ++j;        r[i] = j;    }int id[4][4];memset(id, -1, sizeof(id));for (int k = 0; k < 8; ++k) id[db[k]][dc[k]] = k;vector<array<int, 8>> f(n + 1);for (auto &row : f) row.fill(0);    ll ans = 0;for (int a = n; a >= 1; --a) {if (r[a] == a) continue;                  // 无法到达下一层for (int k = 0; k < 8; ++k) {int b = (db[k] == EMPTY ? 0 : a - db[k]);int c = (dc[k] == EMPTY ? 0 : a - dc[k]);if (db[k] != EMPTY && b < 1) continue;   // 涉及不存在的岛，跳过if (dc[k] != EMPTY && c < 1) continue;int qb = (b == 0 ? a : max(a, r[b]));int qc = (c == 0 ? a : max(a, r[c]));// 下一层路径终点列表的前三项（暂用旧边界 a 表示空项）int A = r[a];int B = max({a, A - 1, qb});int C = max({a, A - 2, min(A - 1, qb), qc});int nextB = (B == a ? EMPTY : A - B);int nextC = (C == a ? EMPTY : A - C);int nextState = id[nextB][nextC];            f[a][k] = (qb - qc) + f[A][nextState];        }        ans += f[a][7];                           // 起点 a 的初始状态为 (a, 空, 空)    }cout << ans << '\n';}intmain(){    freopen("migrate.in", "r", stdin);    freopen("migrate.out", "w", stdout);// ios::sync_with_stdio(false);// cin.tie(nullptr);int c, t;cin >> c >> t;while (t--) solve();return0;}

复杂度与实现细节

• 双指针预处理 O(n)；每岛 8 个状态、每个状态常数次计算 → **单组 O(n)，多组 O(N)**；
• 空间 O(n)：主要数组约 44n 字节，n = 2×10⁶ 时约 84 MiB，1024 MiB 限制下从容；
• 每个 DP 值不超过 n，用 int；总答案和坐标用 long long；
• 多组数据：数组都在 solve() 内局部定义，天然清零，无残留风险。

T4 研发基地：从外层往里剥

思路分析

二分答案 R，验证：能否在树上选出至多 k 个点的子图，形成 ≤ 2 个连通块，且所有点到子图距离 ≤ R？

“恰好 k” → “至多 k”：若 |S| < k，沿块边界不断加入相邻点即可补到 k，块数不增、半径不增。

核心直觉：尽可能选“中心”的节点。反过来想——优先从外层排除。树的最外层是叶子（度数为 1）。当 R ≥ 1 时选叶子没有意义：任何含叶子的合法方案，把叶子换成它唯一的邻居仍合法。于是可以剥掉一轮叶子；剩下的仍是树，再剥一轮……剥 R 轮，被剥掉的点都没必要选。

记剥 R 轮后剩下的图为 T′（空图或树）：

• |T′| ≤ k：直接全选 T′。被剥掉的点 y 到 T′ 的距离 ≤ R（y 在第 < R 轮被剥，它到剩余部分最多 R−1 步）→ 合法 ✓
• |T′| > k：只能选 T′ 的一部分。按度数分类讨论：

于是目标变为：在 T′ 的每条“度 2 链”上，最多能不选多少个连续的度 2 顶点。若最多能不选 len 个，当 |T′| − len ≤ k 时存在合法方案。

链上的覆盖条件：极长度 2 链 v₀, v₁, …, v_m, v_{m+1}（两端必选）。保留 v_p、v_q（p < q），删中间开区间。每个不选的 vᵢ 的

外围分支（被剥掉的部分挂在它上面）必须由两端覆盖：

其中 h_v 是 v 的外层最大深度（剥叶子过程中计算，h_vᵢ = 从 vᵢ 进入被删外层最远能走多少步）。

双指针：对每条链求 L_p（从左端点 p 能连续覆盖到的最右位置）与 B_q（从右端点 q 能连续覆盖到的最左位置），两端覆盖范围联合盖住被删区间 ⟺ 合法条件为

双指针枚举 (p, q) 求最大 len = q − p − 1。每条链耗时线性、链总长 O(n) → 单次判定 O(n)，**总复杂度 O(n log n)**。

15 分解法：子集枚举

n ≤ 10 的测试点，枚举所有大小为 k 的点集：BFS 数连通块（>2 剪掉）+ 全树多源 BFS 求半径：

#include<bits/stdc++.h>usingnamespacestd;int n, k;vector<vector<int>> G;vector<int> dist_;voidsolve(){scanf("%d %d", &n, &k);    G.assign(n + 1, {});for (int i = 1; i < n; i++) {int u, v; scanf("%d %d", &u, &v);        G[u].push_back(v); G[v].push_back(u);    }int best = INT_MAX;for (int mask = 0; mask < (1 << n); mask++) {if (__builtin_popcount(mask) != k) continue;int blocks = 0;                         // 数连通块vector<bool> vis(n + 1, false);for (int v = 1; v <= n; v++)if ((mask >> v & 1) && !vis[v]) {                blocks++;queue<int> q; q.push(v); vis[v] = true;while (!q.empty()) {int u = q.front(); q.pop();for (int w : G[u]) if ((mask >> w & 1) && !vis[w]) { vis[w] = true; q.push(w); }                }            }if (blocks > 2) continue;        fill(dist_.begin(), dist_.end(), -1);   // 多源 BFS 求半径queue<int> q; int r = 0;for (int v = 1; v <= n; v++)if (mask >> v & 1) { dist_[v] = 0; q.push(v); }while (!q.empty()) {int u = q.front(); q.pop();for (int w : G[u]) if (dist_[w] == -1) {                dist_[w] = dist_[u] + 1; r = max(r, dist_[w]); q.push(w);            }        }        best = min(best, r);    }printf("%d\n", best);}intmain(){    freopen("hub.in", "r", stdin);    freopen("hub.out", "w", stdout);int c, t; scanf("%d %d", &c, &t);    dist_.assign(20, -1);while (t--) solve();return0;}

+15 分：k = 2 特判

k = 2 时两个点天然只有 1 或 2 个连通块，约束自动满足——就是经典“树上 2 中心”：二分 R，树形 DP 贪心判定最少中心数 ≤ 2（每个点维护子树内最深未覆盖距离 u 与“已被下方中心覆盖的余量” s，u == R 时就地放中心）。覆盖测试点 7、11、12。满分算法对 k = 2 同样通用，此处从略。

100 分解法：二分 + 剥叶子 + 链上双指针

满分标程

#include<bits/stdc++.h>usingnamespacestd;classFastInput {// n 达 10^6，必须快读staticconstexprint S = 1 << 16;char buf[S]; int pos = 0, len = 0;inlinechargc(){if (pos == len) { len = fread(buf, 1, S, stdin); pos = 0; if (!len) return0; }return buf[pos++];    }public:intread(){int x = 0; char c = gc();while (c < '0' || c > '9') c = gc();while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = gc(); }return x;    }};int n, k;vector<int> head, to, nxt, origDeg;int ecnt;voidaddEdge(int u, int v){    to[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt++;}intcalc(constvector<int>& h, int R){           // 一条链上最多能删多少连续度 2 点int m = (int)h.size() - 2;if (m <= 0) return0;vector<int> L(m + 1), B(m + 2);int j = 1;for (int p = 0; p <= m; ++p) {                // L[p]: 左端点 p 能覆盖到的最右位置        j = max(j, p + 1);while (j <= m && h[j] + j - p <= R) ++j;        L[p] = j - 1;    }    j = m;for (int q = m + 1; q >= 1; --q) {            // B[q]: 右端点 q 能覆盖到的最左位置        j = min(j, q - 1);while (j >= 1 && h[j] + q - j <= R) --j;        B[q] = j + 1;    }int ans = 0, q = 1;for (int p = 0; p <= m; ++p) {        q = max(q, p + 1);while (q <= m + 1 && L[p] + 1 >= B[q]) ++q;        ans = max(ans, q - p - 2);    }return ans;}boolcheck(int R){if (R == 0) return k == n;vector<int> deg = origDeg;vector<int> h(n + 1, 0);vector<unsignedchar> removed(n + 1, 0);vector<int> que(n + 1);int ql = 0, qr = 0;for (int u = 1; u <= n; ++u)if (deg[u] <= 1) que[qr++] = u;int remain = n;                               // 剥 R 轮叶子for (int round = 0; round < R && ql < qr; ++round) {int end = qr;while (ql < end) {int u = que[ql++];if (removed[u]) continue;            removed[u] = 1; --remain;for (int e = head[u]; e != -1; e = nxt[e]) {int v = to[e];if (removed[v]) continue;                h[v] = max(h[v], h[u] + 1);       // 记录外层深度                --deg[v];if (deg[v] == 1) que[qr++] = v;            }        }    }if (remain <= k) returntrue;                 // 剩下的全选即可int need = remain - k;                        // 需要最多不选 need 个连续度 2 点vector<unsignedchar> seen(n + 1, 0);vector<int> chain;int best = 0;for (int u = 1; u <= n; ++u) {                // 找每条极长"度 2 链"if (removed[u] || deg[u] == 2) continue;for (int e = head[u]; e != -1; e = nxt[e]) {int v = to[e];if (removed[v] || deg[v] != 2 || seen[v]) continue;            chain.clear();            chain.push_back(0);                   // 左侧保留端点int pre = u, cur = v;while (deg[cur] == 2) {                seen[cur] = 1;                chain.push_back(h[cur]);int nextNode = -1;for (int f = head[cur]; f != -1; f = nxt[f]) {int w = to[f];if (w != pre && !removed[w]) { nextNode = w; break; }                }                pre = cur; cur = nextNode;            }            chain.push_back(0);                   // 右侧保留端点            best = max(best, calc(chain, R));if (best >= need) returntrue;        }    }returnfalse;}intmain(){    freopen("hub.in", "r", stdin);    freopen("hub.out", "w", stdout);    FastInput in;int c = in.read(), t = in.read();    (void)c;while (t--) {        n = in.read(); k = in.read();        head.assign(n + 1, -1);        origDeg.assign(n + 1, 0);        to.resize(2 * (n - 1)); nxt.resize(2 * (n - 1));        ecnt = 0;for (int i = 1; i < n; ++i) {int u = in.read(), v = in.read();            addEdge(u, v); addEdge(v, u);            ++origDeg[u]; ++origDeg[v];        }int l = 0, r = n - 1;                     // 二分最小可行半径while (l < r) {int mid = l + (r - l) / 2;if (check(mid)) r = mid; else l = mid + 1;        }printf("%d\n", l);    }return0;}

样例 1 演算（链 1−2−3−4−5，k=2）：R=1 时剥 1 轮叶子（剥掉 1、5），T′ = {2,3,4}，remain=3 > 2 → need=1；链 2−3−4 上 h 全 0，L_0 = 1（覆盖 v₁）、B_3 = 2，len = 3−0−2 = 1 ≥ 1 ✓ → 可行；R=0 需 k=n=5 ≠ 2 ✗。答案 1 ✓（第二组同理得 2 ✓）

坑点

• n 达 10⁶、多组数据 t ≤ 5，必须快读（fread 手写读入）；
• 剥叶子的轮数上限是 R（不是剥到空）——被剥的点深度信息 h 依赖恰好剥 R 轮；
• 链的枚举要 seen[] 防重复（同一条链从两端都会被碰到）。

部分分策略总表：考场上先保住兜底

铁律：T1 的梯度断层最小（暴力写好就有 90 分的路线），优先写熟；T3、T4 多组数据，写完先造极限小数据自测；所有 10¹⁸ 量级一律 long long，T1 特判公式用 __int128。

写在最后

这套题的四个信号值得注意：

1. T1 是“连续区间 + 单调性”的完整教学案例——从子集枚举到区间枚举再到双指针，每一步优化都有明确引理支撑，三个引理（连续性、淘汰不回头、每轮最长）值得背下来；
2. T2 的精髓是一句话建模——“坐车不花时间”⟹ 线路缩成一个点，5×10⁵ 个站瞬间塌缩成 500 个点，数据范围 n ≤ 500 就是出题人的提示书；
3. T3 是本轮最精彩的一题——“只保留前三项”的洞察建立在一个朴素的观察上：r 单调，所以判断“第几条路径能延伸到 v”只需要前三大终点。信息论式的降维（整层方案数 → 3 个终点 → 8 个状态）是高级 DP 的通用思维方式；
4. T4 先做约束翻译再做贪心——“恰好 k”翻译成“≤ k”、选点翻译成“从外层剥”，剥完之后度数分类自然浮现，链上双指针是水到渠成的收尾。 四道题的共同点：每一步优化都从一个“反直觉但显然”的观察开始——目标值取最大值、线路缩成一个点、只存前三项、叶子不必选。考场上先找到那个观察，代码只是它的注脚。