代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cassert>
#include<set>
using namespace std;
struct Edge{
	int to,next,value;
}e[100005];
int n,h[50005],m,cnt,ans;
void Add_Edge(int x,int y,int z){
	e[++cnt].to=y;
	e[cnt].next=h[x],e[cnt].value=z;
	h[x]=cnt;
}
int Check(int nnow,int fa,int mid){
	multiset<int> s;
	for(int i=h[nnow];i;i=e[i].next){
		int y=e[i].to;
		if(y==fa)continue;
		int tmp=Check(y,nnow,mid)+e[i].value;
	//	cout<<tmp<<endl;
		if(tmp>=mid)ans++;
		else s.insert(tmp);
	}
	int maxx=0;
	while(!s.empty()){
		int now=*s.begin();
		if(s.size()==1){
			return max(maxx,now);
		}
		auto k=s.lower_bound(mid-now);
	//	cout<<maxx<<endl;
		if(k==s.begin()&&s.count(*k)==1)k++;
		if(k==s.end()){
			maxx=max(maxx,now);
			s.erase(s.find(now));
		}
		else {
			ans++;
			s.erase(s.find(now));
			s.erase(s.find(*k));
		}
	}
	return maxx;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		Add_Edge(x,y,z);
		Add_Edge(y,x,z);
	}
	int l=1,r=5e8,anss=-1;
	//Check(1,0,31);
	//cout<<ans<<endl;
	while(l<=r){
		int mid=(l+r)/2;
		ans=0;
		Check(1,0,mid);
		if(ans>=m)anss=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",anss);
	return 0;
}

评测结果