信竞学习笔记:[CSP-S 2026] 研发基地
这是本人的课堂笔记。
题意
在一个含有 n 个点和 n-1 条边的无根树 T 中,选出 ki 个点组成集合 S,且使它们在形成的连通块不超过 2 个。对于合法的方案 S,定义 d(i) = \min\limits_{j \in S} dist(i, j),其中 dist(i, j) 为点 i 到点 j 的最短路长度。选取合适的 S,使得 \max\limits_{i=1}^n d(i) 最小。求出这个最小值。
思路
“最大值最小”让我们想到二分答案。现在考虑如何编写 check(x) 函数。我们要找到 1 \sim 2 个连通块使得它们到 S 的距离最大为 x。显然,选取点时应尽可能选在树的核心部位,使得到其他节点的距离尽可能平均。那么如何表示这个核心部分呢?由于二分已经使用了 O(\log N) 的复杂度,因此剩下的操作必须在线性时间复杂度内完成。
我们可以考虑逐步删除无根树的叶子节点(也就是度为 1 的节点)。每次删除后都会产生一些新的叶子节点。像这样删除 x 次,那么剩下的节点刚好构成一个连通块,且到被删除的节点的距离一定不超过 x。我们称剩下的这些节点构成一个“核心树”。注意一定要将整层叶子节点删完之后再判断下一轮的叶子结点,不能边删边,边判断。
接下来,我们判断“核心树”剩余的节点数,这个很方便计算,只需在删点时统计即可。我们将其记作 p。如果 p \leq k,可以直接判断这颗“核心树”合法;如果 p > k,那么还需要删除 p - k 个节点才能使“核心树”合法。
在这一步如何选取删除的点呢?我们不能选择“核心树”的叶子节点,因为叶子节点到原本最外层叶子节点的距离恰为 x,如果删除,就会使得有节点到已经删除的节点的距离大于等于 x。我们也不能删除度为 3 的节点,否则会形成超过 2 个连通块。我们删除的节点在“核心树”中必须是一条度为 2 的链。但如果 p > 2x,那么删除后形成的新的两个连通块到链中央的距离超过了 x,不合法。
那么是不是只要是度为 2 的链都能删呢?并不是。如果这条链中有节点与此前被删除的节点相连,那么删除这条链后会导致这些此前被删除的节点的 d 值变大,从而不符合题目要求。
那么如何找到合法的链呢?设我们要删除的点的编号是 S \sim S + (p - k) - 1,其中某个节点编号为 P,那么节点 P 到剩下连通块的距离就是 \min \{P- S + 1, S - P + (p - k) \},这个值必须要小于等于 x - h,其中 h 是节点 P 到第一步被删除的最外层节点的距离。如果不满足,也就是说,P- S + 1 > x - h \land S - P + (p - k) > x - h,我们可以解出 S:x - h - (p - k) + P + 1 \leq S \leq P - x + h。也就是说,对于某个被删除的链上节点 P,其所在链的起点 S 不能位于 A_P = [x - h - (p - k) + P + 1, P - x + h] 区间内。对所有可能的 P,S 不能位于所有 A_P 的并集。
现在的问题是怎么判断是否存在一个点没有被这些区间 A_P 中的任意一个区间覆盖。维护一个差分数组 b,将每个区间 A_P = [L, R] 做如下操作:b_L \leftarrow b_L+1,b_{R+1}\leftarrow b_{R+1}-1,最后做一遍前缀和即可。

