题解 P3000 【[USACO10DEC]牛的健美操Cow Calisthenics】
珅肐
·
·
题解
提供简洁的代码
"目前吸氧最优解"
这道题目总体不难
简单题意：将树中的某些边删去后，使各个连通块中最大直径最小
诶，"最大直径最小"，这不是二分吗
于是我们想到，二分直径的最大长度，显然，由于答案合法的单调性，正确性是可以保证的
那么该如何判断是否可以满足呢？
我们设f[x]表示"从x出发的在x子树中路径的最大长度"
如果"f[x]"加上"max(f[to])"大于我们二分的长度，我们就断边。
（max(f[to]中除去f[x]所到的那个f[to]，即最大的两个f[to]之和大于二分长度，下文皆是此意）
断哪条？
贪心的想，因为"断边后被断的边再也不会产生影响"，所以我们只需要让留下来的边尽可能的小，就留下min(f[x]-1,f[to])+1。
判断的正确性：
因为我们从下往上断边，而且是非断不可时才断，又能保证断边时一定留下最优解，所以判断是正确的。
### 完整代码奉上:
```cpp
#include<iostream>
#include<cstdio>
#include<ctype.h>
using namespace std;
inline int read(){
int x=0,f=0;char ch=getchar();
while(!isdigit(ch))f|=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return f?-x:x;
}
struct Edge{
int next,to;
}edge[200007];
int head[100007],cnt;
int f[100007];
inline void add_edge(int from,int to){
edge[++cnt].next=head[from];
edge[cnt].to=to;head[from]=cnt;
}
int t,n,s;//t表示当前删边的个数
void dfs(int x,int fa,int maxl){
if(t>s)return;//t>s说明不能完成
int lx=0;//lx表示最大f[to]
for(int i=head[x];i;i=edge[i].next){
int to=edge[i].to;if(to==fa)continue;
dfs(to,x,maxl);
if(lx+f[to]>maxl)++t,lx=min(lx,f[to]);//如果需要删边，就保留最小值
else lx=max(lx,f[to]);//否则就更新为最大值
}
f[x]=lx+1;
}
inline bool check(int maxl){
t=0;dfs(1,0,maxl);//注意清空计数器t
return t<=s;
}
int main(){
n=read(),s=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
add_edge(u,v),add_edge(v,u);
}//以上为读入建图
int l=0,r=n/s;//二分下界显然是0，上界其实只要到(n-s)/s向上取正（已经删去了s条边）。
while(l<=r){//普通二分
int mid=l+r>>1;
if(check(mid))r=mid-1;
else l=mid+1;
}
printf("%d\n",l);//输出答案
return 0;//好习惯
}
```
对了，最后说一下二分
```cpp
if(check(mid))r=mid-1;
else l=mid+1;
```
很多人一直对此有疑惑
一般有三种，最常见的好像是$if(check(mid))$后记录一下$ans
这里证明一下我习惯写的
相反，因为在$check$不成立后$l$会$+1$，到最后的极限$l=r$时答案就是正确的