代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50000

using namespace std;

void read(int &x)
{
	char ch=getchar(); x=0;
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
}

struct EDGE {int next,to,w; }edge[N*2+1];
int head[N+1],f[N+1],g[N+1],a[N+1],n,m,cnt=1;
bool bz[N+1];

void add(int u,int v,int w){ edge[cnt]=(EDGE){head[u],v,w},head[u]=cnt++; }

void qsort(int l,int r)
{
	int i=l,j=r,mid=a[l+r>>1];
	while (i<=j)
	{
		while (a[i]<mid) ++i;
		while (a[j]>mid) --j;
		if (i<=j) swap(a[i++],a[j--]);
	}
	if (i<r) qsort(i,r);
	if (j>l) qsort(l,j);
}

void dfs(int k,int last,int mid)
{
 	f[k]=g[k]=0; int tot=0;
	for (int i=head[k];i;i=edge[i].next)
	{
		if (edge[i].to==last) continue;
		dfs(edge[i].to,k,mid);
	}
	for (int i=head[k];i;i=edge[i].next)
	{
		if (edge[i].to==last) continue;
		f[k]+=f[edge[i].to];
		a[++tot]=g[edge[i].to]+edge[i].w;
		if (a[tot]>=mid) ++f[k],--tot;
		else bz[tot]=0;
	}
	if (tot==0) return;
	qsort(1,tot);
	for (int i=1;i<=tot;i++)
	{
		if (bz[i]) continue;
		int j=0;
		for (int l=i+1,r=tot,mid1=l+r>>1;l<=r;a[i]+a[mid1]<mid ? l=mid1+1:r=(j=mid1)-1,mid1=l+r>>1);
		while (bz[j]&&j<=tot) ++j;
		if (j>0&&j<=tot) ++f[k],bz[j]=bz[i]=1;
	}
	for (int i=tot;i>=1;i--) 
		if (! bz[i]){
			g[k]=a[i]; break;
		}
}

int main()
{
	read(n),read(m);
	for (int i=1,x,y,z;i<n;i++) read(x),read(y),read(z),add(x,y,z),add(y,x,z);
	int ans=0;
	for (int l=1,r=500000000,mid=l+r>>1;l<=r;mid=(long long)l+r>>1)
	{
		dfs(1,0,mid);
		if (f[1]>=m) l=(ans=mid)+1;
		else r=mid-1;
	}
	printf("%d",ans);
	return 0;
}

评测结果