CSP-S 2026 D题研发基地题解（5个解法）

零、背景

之前已经分享了历年 CSP-J/S 的比赛题解与《CSP-J 2026 的题解》。

这几天开始分享 CSP-S 2026 比赛题解。
为了避免四道题放在一篇导致文章过长，我计划每道题单独写一篇，最后再给出一个总结。

上篇文章分享了《CSP-S 2026 A题能量水晶（6个解法）》、《CSP-S 2026 B题地铁题解（8个优化）》、《CSP-S 2026 C题迁徙题解（9个解法）》。

这篇文章分享 CSP-S 2026 第四道题「研发基地 hub」的题解。

PS：pdf 题目和源码已经上传网盘，后台回复 CSP-S-2026 获取题目与源码。

一、题目

D 国有 n 座城市，n-1 条道路把它们连成一棵树。
要恰好选 k 座城市建研发基地。
选中的城市在树上必须形成不超过两个连通块。

一座城市的通勤距离，是它到最近一座选中城市之间的道路条数。
选中城市自己的通勤距离是 0。
所有城市通勤距离的最大值，叫这个方案的通勤半径。

问所有合理的建造方案里，通勤半径最小是多少。

二、算法分析

先理解题意。
题目要选 k 个点，这些点形成的图不超过两个连通块。
求其余点到这个连通块的最大距离最小。

最大距离要求最小，显然可以二分答案。
二分一个半径 R，判断能不能让形成的图不超过两个连通块。

定义一个点到叶子的距离为高度。
PS: 我一开始是反向定义的，定义的剩余删除次数。

显然，高度小于 R 的点都不需要选。
只要选高度大于等于 R 的点，高度小于 R 的点就能在 R 距离内到达连通块。
所以判断时，先把所有高度小于 R 的点删掉。

对于剩下的点，要么组成一个连通块，要么是两个连通块。
如果是一个，只要剩下的点数不超过 k，O(1) 就能判断。
如果剩下的点数大于 k，就只能拆成两个连通块。

删掉了高度小于 R 的点之后，这两个连通块肯定是被一条链分割的，可以反证法证明。

此时问题就转化成：给若干个数字，选一个定长的区间，区间上每个点都要满足到左右其中一个端点的距离不超过指定值，问是否存在这样的区间。
暴力枚举是 O(n^2)，所以肯定存在一个 O(n) 的线性算法完成这个判断。

这样，整体复杂度就是 O(n log(n))。

三、如何删点

现在第一个问题是如何删点。
最常见的做法是找一个根，然后 DFS。
要判断一个点能不能删，一种思路是标记到连通块的距离，叶子节点距离设置为 R，分层往上依次减一。
如果有多个儿子时，需要保留最小的距离。

// 从叶子往里剥，maxDis 记每个点还能往外剥几层
bool DfsRemoveLeaf(int u, int pre, int depth) {
  for (int l = 0; l < (int)G[u].size(); l++) {
    const int v = G[u][l];
    if (v == pre) continue;
    if (DfsRemoveLeaf(v, u, depth + 1)) {
      // 儿子删除了，从图中邻接表中删除
      swap(G[u][l], G[u].back());
      G[u].pop_back();
      l--;
      deg[u]--;
      maxDis[u] = min(maxDis[u], maxDis[v] - 1);
    }
  }
  if (pre != -1 && deg[u] == 1 && maxDis[u] > 0) {
    // 自己是叶子，距离在 R 内，删除
    G[u].pop_back();
    deg[u]--;
    leftNode--;
    return true;
  }
  if (depth > maxleafDepth) {  // 记一个没被删除的最深的点，用来换根
    maxleafDepth = depth;
    maxLeafNode = u;
  }
  return false;
}

但这样有个问题：根节点自身可能也需要删掉。

所以还得换一个节点当根，再 DFS 删除一次。

选哪个点呢？
距离叶子距离为 R 的点都删了，没删除的叶子肯定不能删。
第一次 DFS 的时候，顺便记录一个这样的节点，再以它为根重新 DFS 删除一轮即可。

四、如何枚举链

对于一条链，边界要么是叶子，要么是度大于 2 的节点。
所以直接从一个叶子节点当根，遇到度数大于 2 的点，就枚举它的所有边；另一头度数为 2 的，便是一条链的起点，顺着不断循环就能拿到这条链的所有点。

bool IsSplit(int u) { return deg[u] == 1 || deg[u] > 2; }

// 从一个端点构造整条链，左右各加一个桩
bool CheckSplit(int L, int pre) {
  splitNode.clear();
  int u = L, uPre = pre;
  splitNode.push_back(pre);
  splitNode.push_back(u);
  while (!IsSplit(u)) {  // 度数为 2 的点才是链上的点
    for (int v : G[u]) {
      if (v == uPre) continue;
      splitNode.push_back(v);
      uPre = u;
      u = v;
      break;
    }
  }
  int midNum = splitNode.size() - 2;
  int midCanSelectNode = k - (leftNode - midNum);
  // 剪枝
  if (midCanSelectNode < 0) return false; 
  // 得到链后，计算答案
  return CheckRange(midCanSelectNode);
}

bool DfsRemoveLink(int u, int pre) {
  for (int v : G[u]) {
    if (v == pre) continue;
    if (IsSplit(u) && !IsSplit(v) && CheckSplit(v, u)) return true;
    if (DfsRemoveLink(v, u)) return true;
  }
  return false;
}

注意，这里复杂度不是 O(n^2)，而是均摊 O(n)。
因为每条边只属于一条链，只会枚举一次。

五、解法一：暴力判断链（80 分）

设删点后剩 A 个点，链上有 B 个点，链外就是 A - B 个，这些都得选。
A - B > k 时这条链肯定不满足要求。

要保证只剩两个连通块，链上选的点必须是两端连续的部分。链上还能选 M = k - (A - B) 个点，于是链中间有 A - k 个点不能选。

链上的点各自挂着一些已经删掉的分叉，所以不同点需要到连通块的距离限制不一样。
设分叉最长为 x，一个点要被覆盖，就是它到左右选中端点的较小距离加上 x 不超过 R。

具体如代码的 CheckRange函数，暴力做法是固定这个区间，再枚举区间内每个点，看它的较小距离加上分叉长度有没有超过 R。
区间从左滑到右共 B 种，每种都要扫一遍区间，一条链的复杂度为 O(B^2)。
所有链合起来不超过 O(n^2)。
外面套一层二分，总复杂度 O(n^2 log(n))。

得分：80 分。

核心代码如下：

vector<vector<int>> g, G;
vector<int> deg, maxDis, splitNode;
int n, k, leftNode, maxleafDepth, maxLeafNode;

// 枚举左右各选几个，中间一段全部放弃
bool CheckRange(int midCanSelectNode) {
  int midNum = splitNode.size() - 2;
  for (int leftSelect = 0; leftSelect <= midCanSelectNode; leftSelect++) {
    int rightSelect = midCanSelectNode - leftSelect;
    int leftPos = leftSelect + 1;
    int rightPos = midNum - rightSelect;
    bool ok = true;
    for (int i = leftPos; i <= rightPos; i++) {
      int v = splitNode[i];
      int minDis = min(i - leftPos + 1, rightPos - i + 1);
      if (minDis > maxDis[v]) { ok = false; break; }
    }
    if (ok) return true;
  }
  return false;
}


bool Check(const int R) {
  G = g;  // 每次判断都要一份新图
  deg.resize(n + 1);
  maxDis.assign(n + 1, R);
  leftNode = n;
  maxleafDepth = -1;
  for (int i = 1; i <= n; i++) deg[i] = G[i].size();
  DfsRemoveLeaf(1, -1, 0);
  if (leftNode <= k) return true;
  DfsRemoveLeaf(maxLeafNode, -1, 0);  // 换根再剥一轮
  if (leftNode <= k) return true;
  return DfsRemoveLink(maxLeafNode, -1);  // DFS 枚举所有链
}

六、解法二：滑动窗口（80 分）

暴力做法是固定区间后，枚举区间内的点，判断是否可以到达区间的两端。
其实可以反过来看，判断两个端点可以覆盖的最远点。
如果可以把整个区间覆盖，则存在答案。

分三种情况。
左端向右、右端向左，最远点交叉，所有点都能覆盖。
两个最远点相邻，还是能覆盖。
中间留了空档，这些点谁也无法覆盖，这个区间就不是答案。

设左端点 l 最远可以覆盖到 right[l]。
那么 l+1 肯定也能覆盖到 right[l]，因为新端点离得更近。
这样使用双指针，所有左端点的最远覆盖位置就能都算出来了，复杂度 O(n)。

右端点向左同理，复杂度O(n)。
最后枚举所有区间，两个最远位置交叉或者相邻就可行，每种区间 O(1) 判断。

二分的一次判断始终是 O(n)。
综合复杂度 O(n log(n))。

得分：80 分。
复杂度少了一个 n，得分竟然还是 80 分。

核心代码如下：

vector<int> maxLeftToRight, maxRightToLeft;

bool CheckRange(int midCanSelectNode) {
  int midNum = splitNode.size() - 2;
  maxLeftToRight.clear();
  maxLeftToRight.resize(midNum + 2, 0);
  maxRightToLeft.clear();
  maxRightToLeft.resize(midNum + 2, midNum + 1);

  // 左端点 l 向右最远能覆盖的位置，游标只增不减
  int maxRight = 0;
  for (int l = 0; l <= midNum; l++) {
    while (maxRight <= midNum && maxDis[splitNode[maxRight]] >= maxRight - l) {
      maxRight++;
    }
    maxLeftToRight[l] = maxRight - 1;
  }

  // 右端点 r 向左最远能覆盖的位置
  int minLeft = midNum + 1;
  for (int r = midNum + 1; r > 0; r--) {
    while (minLeft > 0 && maxDis[splitNode[minLeft]] >= r - minLeft) {
      minLeft--;
    }
    maxRightToLeft[r] = minLeft + 1;
  }

  for (int l = 0, r = midNum + 1 - midCanSelectNode; l <= midCanSelectNode; l++, r++) {
    if (maxLeftToRight[l] + 1 >= maxRightToLeft[r]) return true;
  }
  return false;
}

七、解法三：常数优化（85 分）

由于被卡常数了，所以需要进行常数优化。

首先，可以把所有的一维 vector 都换成定长数组。
对于图，是二维的，可以缓存数组邻接表。
输入数据量比较大，换成 fastRead。

复杂度还是 O(n log(n))。
得分：85 分。

核心代码如下：

int deg[max6];

struct Graph {
  int fir[N], toV[M], nextV[M], cnt, deg[N];
  void AddEdge(const int u, const int v) {
    toV[cnt] = v;
    nextV[cnt] = fir[u];
    fir[u] = cnt++;
    deg[u]++;
  }
  void Init() {
    memset(fir, 0, sizeof(int) * (n + 2));
    memset(deg, 0, sizeof(int) * (n + 2));
    cnt = 1;
  }
  int Len(int u) { return deg[u]; }
};

void CloneGraph(const Graph& g, Graph& GG) {
  GG.Init();
  for (int u = 1; u <= n; u++) {
    for (int p = g.fir[u]; p != 0; p = g.nextV[p]) {
      GG.AddEdge(u, g.toV[p]);
    }
  }
}

char readWritebuf[20];
inline ll FastRead() {
  scanf("%s", readWritebuf);
  ll v = 0;
  for (const char* p = readWritebuf; *p; p++) {
    v = v * 10 + (*p - '0');
  }
  return v;
}

八、解法四：三个剪枝（95 分）

回顾算法流程：二分、复制图、两轮DFS删点、枚举链。

第一轮 DFS 删点之后，可能就满足一个连通块了，可以提前判断。
第二轮 DFS 删点之后，再判断依次。

而接下来这个剪枝，很容易忽略。

假设剩余 leftNode 个点，名额只有 k 个，得继续删除 leftNode - k 个点，而且它们只能落在一条链上。
链两端各有一片选中点，每片沿着链最多往内覆盖 R 步，合起来最多覆盖 2R 个链上点。
如果要删的点超过 2R，无论挑哪条链都没答案，可以直接剪枝。

复杂度不变，最坏还是 O(n log(n))。
得分：95 分。

核心代码如下：

bool Check(const int R) {
  CloneGraph(g, G);
  for (int i = 1; i <= n; i++) {
    deg[i] = G.Len(i);
    maxDis[i] = R;
  }
  leftNode = n;

  DfsRemoveLeaf(1, -1, 0);
  if (leftNode <= k) return true;  // 剪枝一：一个连通块就装得下

  DfsRemoveLeaf(maxLeafNode, -1, 0);  // 换根再删一轮
  if (leftNode <= k) return true;  // 剪枝二：一个连通块就装得下

  int maxLinkRemove = leftNode - k;
  if (maxLinkRemove > 2 * R) {
    return false;  // 剪枝三：两端最多覆盖 2R 个点
  }
  return DfsRemoveLink(maxLeafNode, -1);
}

九、解法五：满分优化（100 分）

先数一遍现在一次判断要花几个 O(n)。
存在删点，所以把图复制了一遍，这里一个 O(n)。
为了删点，用了两次 DFS，两个 O(n)。
最后枚举链，又一个 O(n)。

之所以复制图，是为了删点。
之所以真的删点，是因为点与叶子的关系定义成了剩余删除次数，R 一变，这个值跟着变。
如果定义成到叶子的高度，不管 R 怎么变，高度永远不变。

由于高度不随 R 变化，所以可以预处理一次计算好。

所有叶子高度记 1 或 1，进队列。
弹出一个点，把邻居度数减一；
某个邻居度数降到 1，说明它成了新叶子，高度是当前儿子高度加一，再进队列。

第一个问题：此时如何删除点呢？
有了高度表，就不需要真的删点了。
高度小于 R 的点需要删除，用到时判断一下点是否删掉即可。

第二个问题是如何统计删了多少个点。
也很简单，循环一遍统计高度小于 R 的个数。

第三个问题：删除点后，节点的度数发生了变化。所以，需要循环一遍重算。

第四个问题是 DFS 要调用很多次函数，很耗时间。
消除递归：枚举所有点，判断是不是链的一个端点，是了就构造链进行判断。
一条链会被两端各发现一次，但每条边只属于一条链，整体仍是均摊 O(n)。

这些优化叠加在一起，总复杂度不变还是 O(n log(n))。
但是可以得分 100 分。

核心代码如下：

// 1. 高度只算一次
void InitDegAndMaxDis() {
  queue<int> q;
  deg.resize(n + 1, 0);
  maxDis.resize(n + 1, 0);
  for (int u = 1; u <= n; u++) {
    deg[u] = g[u].size();
    if (deg[u] == 1) {
      maxDis[u] = 1;
      q.push(u);
    }
  }
  while (!q.empty()) {
    const int u = q.front();
    q.pop();
    for (int v : g[u]) {
      deg[v]--;
      if (deg[v] == 1) {
        maxDis[v] = maxDis[u] + 1;
        q.push(v);
      }
    }
  }
}

// 2. 二分时，不复制图、不删点，直接查表判断
bool Check(const int mid) {
  R = mid;
  leftNode = n;
  for (int i = 1; i <= n; i++) {
    if (maxDis[i] <= R) leftNode--;  // 高度不够，算作删掉
  }
  if (leftNode <= k) return true;
  if (leftNode - k > 2 * R) return false;

  // 重算未删除节点的度
  for (int u = 1; u <= n; u++) {
    deg[u] = 0;
    if (maxDis[u] <= R) continue;
    for (int v : g[u]) {
      if (maxDis[v] > R) deg[u]++;
    }
  }

  // 3. 循环所有点找链的端点，去掉递归
  for (int u = 1; u <= n; u++) {
    if (deg[u] <= 0 || deg[u] == 2) continue;
    for (int v : g[u]) {
      if (deg[v] != 2) continue;  // 链上必须有节点
      if (CheckSplit(v, u)) return true;
    }
  }
  return false;
}

// 4. 链上算出每个点允许往外伸的步数
bool CheckSplit(const int L, const int pre) {
  // 与暴力一致
}

十、总结

这道题很容易想到 O(n^2 log(n)) 的解法，然后拿到 80 分。
滑动窗口消掉一个 n，得到 O(n log(n))，竟然还是 80 分。
换数组邻接表、换快速读入，涨到 85 分。
再加三个剪枝，涨到 95 分。

最后 5 分比赛的时候应该得不到了。
把递归去掉，最终得到 100 分。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code

本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。

CSP-S 2026 D题研发基地题解（5个解法）

零、背景

一、题目

二、算法分析

三、如何删点

四、如何枚举链

五、解法一：暴力判断链（80 分）

六、解法二：滑动窗口（80 分）

七、解法三：常数优化（85 分）

八、解法四：三个剪枝（95 分）

九、解法五：满分优化（100 分）

十、总结

关注公众号,接收最新消息

置顶文章

目录

CSP-S 2026 D题 研发基地 题解（5个解法）

零、背景

一、题目

二、算法分析

三、如何删点

四、如何枚举链

五、解法一：暴力判断链（80 分）

六、解法二：滑动窗口（80 分）

七、解法三：常数优化（85 分）

八、解法四：三个剪枝（95 分）

九、解法五：满分优化（100 分）

十、总结

关注公众号,接收最新消息

置顶文章

目录

CSP-S 2026 D题研发基地题解（5个解法）