代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register
#define in(s) freopen(s".in","r",stdin)
#define out(s) freopen(s".out","w",stdout)
inline int read(){
	int x=0,k=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return k*x;
}
inline void wr(rg int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) wr(x/10);
	putchar(x%10+'0');
}
const int N=5e4+10;
int n,m,tot,to[N<<1],c[N<<1],nxt[N<<1],head[N],sum,dep[N],sr[N][2],maxx,numm,ot[N],ww[N],a[N],minn=0x3f3f3f3f,he[N];
bool flag=1;
inline void add_edge(rg int u,rg int v,rg int w){
	to[++tot]=v;
	c[tot]=w;
	nxt[tot]=head[u];
	head[u]=tot;
	to[++tot]=u;
	c[tot]=w;
	nxt[tot]=head[v];
	head[v]=tot;
}
inline void dfs1(int x,int fa){
    for(int i=head[x];i;i=nxt[i]){
        int v=to[i];
    	if(v==fa)continue;
        dfs1(v,x);
        a[x]=c[i];
    }
}
inline bool check(rg int s){
	int num=0,now=0;
    for(int i=1;i<n;i++){
        if(now+a[i]>=s)now=0,num++;
        else now+=a[i];
    }
    return num>=m;
}
inline void dfs(rg int x,rg int fa){
	dep[x]=dep[fa]+1;
	for(rg int i=head[x];i;i=nxt[i]){
		int v=to[i];
		if(v==fa)continue;
		dfs(v,x);
		if(sr[v][0]+c[i]>sr[x][0])sr[x][1]=sr[x][0],sr[x][0]=sr[v][0]+c[i];
		else if(sr[v][0]+1>sr[x][1])sr[x][1]=sr[v][0]+c[i];
	}
	maxx=max(maxx,sr[x][0]+sr[x][1]);
}
inline bool cmp(int a,int b){
	return a>b;
}
inline void jh(){
    sort(ww+1,ww+n,cmp);
    int ans=2147483647;
    for(int i=1;i<=m;i++)
        ans=min(ans,ww[i]+ww[2*m-i+1]);
    wr(ans);
}
vector<int>ve[N];
inline int check1(rg int x,rg int mid1,rg int mid){
    int nums=0;
   	for(rg int i=ve[x].size()-1,j=0;j<i;){
   		if(i==mid1)i--;
   		if(j==mid1)j++;
   		if(j>=i)break;
		if(ve[x][i]+ve[x][j]<mid)j++;
		else nums++,i--,j++;
	}
    return nums;
}
inline void dfs3(rg int x,rg int fa,rg int mid){
	for(rg int i=head[x];i;i=nxt[i]){
		int v=to[i];
		if(v==fa)continue;
		dfs3(v,x,mid);
		he[v]+=c[i];
		if(he[v]>=mid)numm++;
        else ve[x].push_back(he[v]);
	}
	sort(ve[x].begin(),ve[x].end());
	int nm=0;
	for(rg int i=ve[x].size()-1,j=0;j<i;){
		if(ve[x][i]+ve[x][j]<mid)j++;
		else nm++,i--,j++;
	}
    numm+=nm;
    if((nm<<1)==ve[x].size())return;
    int l=0,r=ve[x].size()-1,as=0;
    while(l<=r){
    	int mid1=l+r>>1;
        if(check1(x,mid1,mid)>=nm)as=mid1,l=mid1+1;
        else r=mid1-1;
    }
    he[x]=ve[x][as];
}
int main(){
	#ifndef D
//	in("track");
//	out("track");
	#endif
	n=read(),m=read();
	for(rg int i=1,u,v,w;i<n;i++){
		u=read(),v=read(),w=read();
		ww[i]=w;
		sum+=w;
		minn=min(minn,w);
		if(v!=u+1)flag=0;
		add_edge(u,v,w);
		ot[u]++,ot[v]++;
	}
	if(m==1){
		dfs(1,0);
		wr(maxx);
		return 0;
	}
	if(ot[1]==n-1){
		jh();
		return 0;
	}
	if(flag){
		dfs1(1,0);
        int l=1,r=sum+1,ans=0;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid))ans=mid,l=mid+1;
            else r=mid-1;
        }
        wr(ans);
		return 0;
	}
	if(m==n-1){
		wr(minn);
		return 0;
	}
	int l=1,r=sum/m,ans=0;
	while(l<=r){
		memset(he,0,sizeof(he));
		for(rg int i=1;i<=n;i++)ve[i].clear(); 
		numm=0;
		int mid=l+r>>1;
		dfs3(1,0,mid);
		if(numm>=m)ans=mid,l=mid+1;
		else r=mid-1;
	} 
	wr(ans);
	return 0;
}
//10 3
//1 2 1
//2 3 2
//3 4 1
//4 5 2
//5 6 1
//6 7 2
//7 8 1
//8 9 2
//9 10 1

//8 3
//1 2 1
//1 3 2
//1 4 1
//1 5 2
//1 6 1
//1 7 2
//1 8 1

评测结果