自动搬运

查看原文

来自洛谷，原作者为

	珅肐 你没有如期归来，而这正是离别的意义。

搬运于2025-08-24 21:44:15，当前版本为作者最后更新于2019-10-13 10:53:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供简洁的代码

"目前吸氧最优解"

这道题目总体不难

简单题意：将树中的某些边删去后，使各个连通块中最大直径最小

诶，"最大直径最小"，这不是二分吗

于是我们想到，二分直径的最大长度，显然，由于答案合法的单调性，正确性是可以保证的

那么该如何判断是否可以满足呢？

我们设$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$。

$min(f[x]-1,f[to])$表示儿子的最大路径长度，$+1$表示加上儿子到父亲的边。

判断的正确性：

因为我们从下往上断边，而且是非断不可时才断，又能保证断边时一定留下最优解，所以判断是正确的。

完整代码奉上:

#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;//好习惯
}

对了，最后说一下二分

if(check(mid))r=mid-1;
else l=mid+1;

很多人一直对此有疑惑

一般有三种，最常见的好像是$if(check(mid))$后记录一下$ans$

这里证明一下我习惯写的

$if(check(mid))$后$r$会$-1$，所以$r$不一定是最终答案

相反，因为在$check$不成立后$l$会$+1$，到最后的极限$l=r$时答案就是正确的