tle 75pts. 提交记录

#include<bits/stdc++.h>
using namespace std;
int n,k,x,y,z;
int le=1,ri=5e8+10,mid;
vector<pair<int,int> > e[50050];
int ans;
int vis[50050];
int dfs(int u,int fa){
	if(vis[u]) return 0;
	vis[u]=1;
	multiset<int> s;
	s.clear();
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i].second,w=e[u][i].first;
		if(v==fa) continue;
//		int v1=dfs(v,u);
		w+=dfs(v,u);
		if(w>=mid){
			ans++;
			continue;
		}
	//	printf("%d %d %d\n",v,u,w);
		s.insert(w);
	}
/*	printf("%d %d :: \n",u,fa);
	for(auto it=s.begin();it!=s.end();it++){
		printf("%d ",(*it));
	}
	printf("\n");*/
	while(!s.empty()){
		auto it=--s.end();
		int u=*it;
		if(s.size()==1) return u;
		if(s.empty()) return 0;
		auto it1=lower_bound(s.begin(),s.end(),mid-u);
		if(it1==s.end()||it1==it) return u;
		int v=*it1;
		s.erase(it1);
		auto it2=lower_bound(s.begin(),s.end(),mid-v);
		s.erase(it2);
		ans++;
	}
//	printf("%d\n",ans);
	return 0;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		e[x].push_back({z,y});
		e[y].push_back({z,x});
	}
	while(le<ri){
		mid=(le+ri+1)/2;
//		printf("%d %d %d\n",le,ri,mid);
		ans=0;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++){
			if(!vis[i]) dfs(i,0);
		}
//		printf("%d\n",ans);
		if(ans>=k){
			le=mid;
		}
		else{
			ri=mid-1;
		}
	}
	printf("%d\n",le);
}