代码

#include<bits/stdc++.h>
using namespace std;
int getint(){
	int ans=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*f;
}
const int N=100010,M=N<<1;

struct bian{
	int l,e,n;
};
bian b[M];
int s[N],tot=0;
void add(int x,int y,int z){
	tot++;
	b[tot].l=z;
	b[tot].e=y;
	b[tot].n=s[x];
	s[x]=tot;
}

long long maxson[N];
int cnt=0,mid=0;
multiset<long long> sons;
void ss(int x,int fa){
	//cout<<">>>"<<x<<endl;
	for(int i=s[x];i;i=b[i].n){
		if(b[i].e==fa)continue;
		ss(b[i].e,x);
	}
	sons.clear();
	for(int i=s[x];i;i=b[i].n){
		if(b[i].e==fa)continue;
		sons.insert(maxson[b[i].e]+b[i].l);
	}
	multiset<long long>::reverse_iterator it=sons.rbegin();
	while(sons.size()){
		if(*it>=mid){
			cnt++;
			sons.erase(sons.find(*it));
		}else break;
	}
	while(sons.size()){
		int t=*sons.begin();
		sons.erase(sons.begin());
		multiset<long long>::iterator itt=sons.lower_bound(mid-t);
		if(itt==sons.end())maxson[x]=t;
		else cnt++,sons.erase(itt);
	}
	//cout<<">> "<<x<<" "<<maxson[x]<<endl;
}
int main(){
	int n=getint(),m=getint();
	long long sum=0;
	for(int i=0;i<n-1;i++){
		int x=getint(),y=getint(),z=getint();
		add(x,y,z);
		add(y,x,z);
		sum+=z;
	}
	long long l=0,r=sum/m+1;
	while(l<r){
		mid=(l+r+1)>>1;
		cnt=0;
		memset(maxson,0,sizeof(maxson));
		ss(2,0);
		if(cnt>=m)l=mid;
		else r=mid-1;
		//cout<<"---"<<mid<<"---"<<endl;
	}
	cout<<l;
	return 0;
}

评测结果