思路
看到最大值最小首先可以想到二分，发现答案具有单调性，那么思考如何在 \(O(n)\) 的时间内判断是否合法。
考虑贪心，在最远没覆盖的点的距离和要判断的 \(mid\) 刚好相等的时侯再选择一定不劣，因为这样覆盖的点最多，那么从叶子节点向上回溯，处理它的所有儿子，判断是否选择该点。
注意事项
-
因为一个点也可以被它的儿子覆盖，所以选完一个点以后应该将值设为 \(-mid\) 而不是 \(0\)。
-
判断大小时的大小于号最好模一遍样例再确定，
不然容易被硬控 2h。 -
判叶子节点的时候要注意入度为 \(1\) 的点除了叶子节点外，也可能是根节点（可能就我会犯吧）。
-
合并到根节点的时候要特判其是否能被覆盖。
-
儿子可以被其他儿子内的关键点覆盖。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k,ans,mid,tim;
int dep[N];
vector<int>v[N];
inline void dfs(int x,int fa)
{
if(v[x].size()==1&&x!=1) //判叶子
{
dep[x]=1;
return ;
}
dep[x]=-N; //儿子节点的信息
int mi=N; // 距离最近的关键点
for(auto y : v[x])
if(y!=fa)
{
dfs(y,x);
dep[x]=max(dep[x],dep[y]);
mi=min(mi,dep[y]);
}
dep[x]+=1; // 加上自己
if(dep[x]+mi<=0) // 能否被儿子的关键点覆盖
dep[x]=mi+1;
else if(dep[x]>mid) // 自己是关键点
{
dep[x]=-mid;
tim++;
}
if(x==1&&dep[x]>0) // 特判根节点
tim++;
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for(int i=2,x,y;i<=n;i++)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
int l=1,r=n;
while(l<=r)
{
mid=l+r>>1;
tim=0;
dfs(1,0);
if(tim<=k)
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
cout<<ans<<"\n";
return 0;
}