研发基地

固定半径的核心

先二分半径R。R=0当且仅当k=n。对R>0，将树按轮次同步剥掉叶子，做R轮，剩余树记为C。记录每个核心点v所连已剥掉分支的最大高度h[v]（没有分支时为0）。若C为空或大小≤k，则一个连通块即可覆盖，之后向相邻点扩展到恰好k个点不会增加连通块数或半径。

为什么只用删一段链

当|C|>k≥2时，可以把核心外的已选点移向它们与C的连接点：每个剥离分支相对连接点的高度≤R，投影不会破坏覆盖且不增加所选点数或连通块数。因此可假定选点位于C。

C的每个叶端都有深度恰好R的外侧分支，故该核心叶子必须被选中，否则最远叶子的距离>R。核心中度数至少3的点也必须选中：不选它会将至少三个含核心叶子的分支分开，产生至少三个选中连通块。

所以所有未选核心点必须是同一条度2链上的连续区间；删掉两个不同区间会产生至少三个连通块。区间两端的核心点均保留。若删除区间内第j点的高度为h_j，则它以及附着分支能被覆盖，当且仅当h_j+min(到左端保留点的距离,到右端保留点的距离)≤R。

单调队列判定

需要至少删G=|C|-k个核心点。如果可删更长一段，也能只删其中G点，所以只判长度G的窗口。窗口前ceil(G/2)个点取左侧距离，后floor(G/2)个取右侧距离，条件分别是h[j]+j和h[j]-j的窗口最大值不越界。两条单调队列可在线性时间扫完每条核心链。

剥叶及链扫描均O(n)，每次二分判定O(n)，总时间O(n log n)，空间O(n)。先从任意根做一次BFS，以该根的最大距离作为二分可行上界：选中该根，再沿相邻点扩展到恰好k个点即可保持连通和覆盖。这能避免浅树上从n开始二分所产生的无意义全树剥叶轮次，最坏复杂度不变。用邻接表和迭代队列，避免百万节点递归爆栈。独立oracle枚举k点子集，检查选中诱导图连通块数，再多源BFS求真实半径；另有2500棵小随机树的原型交叉验证。

难度依据

8 / geekpi-9-v2：二分半径、树叶剥离核心、证明两个连通块仅能删一段链，再用单调队列判定覆盖，需完整结构证明。

参考程序

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Fast{static const int Z=1<<20;char b[Z];int p=0,n=0;char get(){if(p==n){n=fread(b,1,Z,stdin);p=0;if(!n)return 0;}return b[p++];}int read(){char c;do c=get();while(c&&c<=32);int x=0;while(c>='0'&&c<='9'){x=x*10+c-'0';c=get();}return x;}}in;
int main(){in.read();int T=in.read();while(T--){int n=in.read(),k=in.read();vector<int>head(n,-1),to(2*n-2),nxt(2*n-2),deg0(n),deg(n),h(n),round(n),q(n),chain;int ec=0;auto add=[&](int u,int v){to[ec]=v;nxt[ec]=head[u];head[u]=ec++;deg0[u]++;};for(int i=1;i<n;i++){int u=in.read()-1,v=in.read()-1;add(u,v);add(v,u);}vector<int>dq1(n),dq2(n);int upper=0,bfsFront=0,bfsBack=0;q[bfsBack++]=0;round[0]=1;while(bfsFront<bfsBack){int u=q[bfsFront++];upper=max(upper,round[u]-1);for(int e=head[u];e!=-1;e=nxt[e]){int v=to[e];if(!round[v]){round[v]=round[u]+1;q[bfsBack++]=v;}}}auto check=[&](int R){if(R==0)return k==n;deg=deg0;fill(h.begin(),h.end(),0);fill(round.begin(),round.end(),0);int front=0,back=0,core=n;for(int i=0;i<n;i++)if(deg[i]<=1){q[back++]=i;round[i]=1;}while(front<back){int u=q[front++];if(round[u]>R)break;core--;for(int e=head[u];e!=-1;e=nxt[e]){int v=to[e];if(round[v]&&round[v]<=round[u])continue;deg[v]--;h[v]=max(h[v],h[u]+1);if(deg[v]==1&&!round[v]){round[v]=round[u]+1;q[back++]=v;}}}if(core<=k)return true;int need=core-k,left=(need+1)/2;auto removed=[&](int u){return round[u]&&round[u]<=R;};for(int start=0;start<n;start++){if(removed(start)||deg[start]==2)continue;for(int ee=head[start];ee!=-1;ee=nxt[ee]){int cur=to[ee];if(removed(cur))continue;chain.clear();int prev=start;while(deg[cur]==2){chain.push_back(cur);int step=-1;for(int e=head[cur];e!=-1;e=nxt[e])if(to[e]!=prev&&!removed(to[e])){step=to[e];break;}prev=cur;cur=step;}int L=chain.size();if(start>cur||L<need)continue;int a1=0,b1=0,a2=0,b2=0,added1=-1,added2=-1;for(int s=0;s+need<=L;s++){while(added1<s+left-1){int j=++added1;while(b1>a1&&h[chain[dq1[b1-1]]]+dq1[b1-1]<=h[chain[j]]+j)b1--;dq1[b1++]=j;}while(a1<b1&&dq1[a1]<s)a1++;while(added2<s+need-1){int j=++added2;if(j<s+left)continue;while(b2>a2&&h[chain[dq2[b2-1]]]-dq2[b2-1]<=h[chain[j]]-j)b2--;dq2[b2++]=j;}while(a2<b2&&dq2[a2]<s+left)a2++;if(h[chain[dq1[a1]]]+dq1[a1]-s+1<=R&&(need==left||h[chain[dq2[a2]]]-dq2[a2]+s+need<=R))return true;}}}return false;};int lo=0,hi=upper;while(lo<hi){int mid=(lo+hi)/2;if(check(mid))hi=mid;else lo=mid+1;}printf("%d\n",lo);}}

本参考解为独立编写的训练参考解，非官方标准程序。测试数据为自建训练数据。