用二分答案。

dfs，每次求出以他为根的所有链，排序后看看需不需要断掉。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
#define N 100005
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e-'0');
		e=getchar();
	}
	return x*y;
}
bool cmp(int A,int B){
	return A>B;
}
int n,m,cnt;
int head[N],ver[N<<1],nxt[N<<1],idx=-1;
int dep[N],t[N];
void add(int x,int y){
	++idx,ver[idx]=y,nxt[idx]=head[x],head[x]=idx;
}
void dfs(int u,int fa,int k){
	for(int i=head[u];~i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		dfs(v,u,k);
	}
	int tot=0;
	for(int i=head[u];~i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		t[++tot]=dep[v]+1;
	}
	if(!tot){
		return ;
	}
	sort(t+1,t+1+tot,cmp);
	int j=1;
	t[tot+1]=0;
	while(j<=tot&&t[j]+t[j+1]>k)++cnt,++j;
	dep[u]=t[j]; 
}
signed main() {
	memset(head,-1,sizeof head);
	R(n),R(m);
	for(int i=1;i<n;++i){
		int R(x),R(y);
		add(x,y),add(y,x);
	}
	int l=1,r=N,mid,ans;
	while(l<=r){
		memset(dep,0,sizeof dep);
		memset(t,0,sizeof t);
		mid=(l+r)/2,cnt=0;
		dfs(1,0,mid);
		if(cnt<=m)r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans<<"\n";
	return 0;
}

阿拉伯文版题解

أولا ، بعد أن رأينا هذا السؤال ، وجدنا أننا يمكن أن تستخدم فقط نصف الإجابة . ثم في الاختيار ، ونحن استخدام إدارة الدعم الميداني لتسجيل كيف العديد من الحواف تحتاج إلى قطع كل عقدة ، ونحن تسجيل أطول سلسلة و سلسلة طويلة في الشجرة الفرعية مع جذورها ، والفرز ، إذا كان طول أطول سلسلة + سلسلة طويلة أقل من دولار > $ م ، ثم يجب أن تقطع أطول سلسلة ، ثم تكرار حزب الشعب الكمبودي

void dfs(int u,int dad,int k){
	for(int i=head[u];i;i=a[i].nxt){
		int v=a[i].v;
		if(v==dad) continue;
		dfs(v,u,k);
	}
	int ret=0;
	for(int i=head[u];i;i=a[i].nxt){
		int v=a[i].v;
		if(v==dad) continue;
		t[++ret]=dep[v]+1;
	}
	if(!ret){
		dep[u]=0;
		return;
	}
	sort(t+1,t+ret+1,cmp);
	int p=1;
	t[ret+1]=0;
	while(p<=ret&&t[p]+t[p+1]>k) cnt++,p++;
	dep[u]=t[p];
}

首先我们看到这个题目之后发现只能使用二分答案

然后在check的时候我们用dfs来记录需要剪掉多少条边

我们对于每一个节点记录出以它为根的子树里的最长链与次长链，并排序，如果最长链+次长链的长度 $>m$ 那么一定要把最长链剪掉，并依次递归下去即可

void dfs(int u,int dad,int k){
	for(int i=head[u];i;i=a[i].nxt){
		int v=a[i].v;
		if(v==dad) continue;
		dfs(v,u,k);
	}
	int ret=0;
	for(int i=head[u];i;i=a[i].nxt){
		int v=a[i].v;
		if(v==dad) continue;
		t[++ret]=dep[v]+1;
	}
	if(!ret){
		dep[u]=0;
		return;
	}
	sort(t+1,t+ret+1,cmp);
	int p=1;
	t[ret+1]=0;
	while(p<=ret&&t[p]+t[p+1]>k) cnt++,p++;
	dep[u]=t[p];
}

场上竟然没有切掉。。。

显然二分

考虑我们想要把一个树砍成一个森林且每个直径都不超过一个 $lenth$ ，当且仅当我们把所有长度超过它的链条全部砍掉。

然后我们发现任何一条链都是两个端点，然后一直跳到上面的 $lca$ 这样一条链。

我们考虑以每一个点作为 $lca$ ，并且用自己子树里的某两条链条拼成长链条，如果超过了 $lenth$ 就一定要砍掉一个。

显然，如果两个点以 $a$ 为 $lca$ 当且仅当这两个点在 $a$ 的两个儿子的子树当中，否则一定存在更深的公共祖先。

于是我们的 $chk$ 函数考虑 $dfs$ ，对于每一个点记录一下它的子树里面砍掉一定要砍的边以后的最深深度，然后我们上传的时候，只要把一个节点所有儿子的最深深度 $sort$ 一下，从大到小进行匹配即可。

时间复杂度 $O(nlog^2n)$

CODE

#include<bits/stdc++.h>
using namespace std;
vector<int>G[100005];
int cnt,d[100005],now;
void dfs(int x,int fa){
	d[x]=0;
//	cout<<x<<endl;
	vector<int>vec;
	for(int i=0; i<G[x].size(); i++){
		int y=G[x][i];
		if(y==fa)continue;
		dfs(y,x);
		vec.push_back(d[y]);
//		cout<<d[y]<<",";
	}vec.push_back(0);
	sort(vec.begin(),vec.end());
//	cout<<x<<endl;
//	for(int i=0; i<vec.size(); i++)printf("%d,",vec[i]);
	d[x]=vec[vec.size()-1];
//	cout<<endl;
	for(int i=vec.size()-1; i>0; i--){
		int d1=vec[i],d2=vec[i-1];
		if(d1+d2+1>=now){
			d[x]=d2;
			cnt++;
		}else{
			break;
		}
	}d[x]++;
}
int main(){
//	freopen("森林直径ex.in","r",stdin);
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1; i<n; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y),G[y].push_back(x);
	}int l=1,r=n;
	while(r-l>1){
		int mid=l+r>>1;now=mid,cnt=0;
//		cout<<l<<" "<<r<<" "<<now<<endl;
		dfs(1,1);
//		cout<<l<<" "<<r<<" "<<cnt<<endl;
		if(cnt<=m)r=mid;
		else l=mid+1;
	}int ans;
	now=l,cnt=0;
	dfs(1,1);
	if(cnt<=m)ans=l;
	else ans=r;
	cout<<ans-2;
	return 0;
}/*
9 3
1 2
1 3
3 4
3 5
5 7
5 6
5 8
5 9


*/