代码

#include<bits/stdc++.h>
using namespace std;

int n,m,c,head[100100],dis[100100],mid,rem;
bool vis[100100];

struct Edge{
	int to,nxt,w;
}e[100100];

void read()
{
	int m1,m2,m3;
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&m1,&m2,&m3);
		e[++c].to=m2;
		e[c].nxt=head[m1];
		head[m1]=c;
		e[c].w=m3;
		
		e[++c].to=m1;
		e[c].nxt=head[m2];
		head[m2]=c;
		e[c].w=m3;
	}
}

void dfs(int k,int fa)
{
	if(rem<=0)return;
	for(int i=head[k];i;i=e[i].nxt)
	{
		if(e[i].to==fa)continue;
		dfs(e[i].to,k);
		if(e[i].w+dis[e[i].to]>=mid)rem--,vis[i]=1;
	}
	//cout<<"GO1"<<endl;
	multiset<int>mtst;
	for(int i=head[k];i;i=e[i].nxt)
	{
		if(!vis[i] && e[i].to!=fa)mtst.insert(e[i].w+dis[e[i].to]);
	}
	//cout<<"GO2"<<endl;
	multiset<int>::iterator iit;
	for(multiset<int>::reverse_iterator it=mtst.rbegin();it!=mtst.rend();it++)
	{
		iit=mtst.lower_bound(mid-*it);
		if(iit==mtst.end() || *iit>=*it)
		{
			dis[k]=*it;
			break;
		}
		rem--;
		mtst.erase(iit);
	}
	//cout<<"GO3"<<endl;
}

bool check()
{
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	rem=m;
	dfs(1,1);
	return rem<=0;
}

int main()
{
	read();
	int l=1,r=0x7fffffff-1,ans;
	while(l<=r)
	{
		//printf("#%d,%d\n",l,r);
		mid=(l+r)>>1;
		if(check())ans=mid,l=mid+1;
		else r=mid-1;
	}
	cout<<ans;
} 

评测结果