树形结构不带树上算法走典型。
用(DFS)，即可，考虑的方向不能脱离树状结构。
即考虑一棵子树中分出的路线一定是独立的，而那些没用的边可以传上去作为备选答案。
再考虑一个贪心，我们每次上传最大的即可。
#include<bits/stdc++.h>
using namespace std;
namespace AE86
{
const int bufl=1<<15;
char buf[bufl],*s=buf,*t=buf;
inline int fetch()
{
if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
return*s++;
}
inline int read()
{
int a=0,b=1,c=fetch();
while(!isdigit(c)) b^=c=='-',c=fetch();
while(isdigit(c)) a=a*10+c-48,c=fetch();
return b?a:-a;
}
}
const int N=5e4+10;
int n,m,num_edge,Sum,Ans;
int head[N<<1],Dis[N];
struct Edge{int next,to,dis;} edge[N<<1];
inline void Add(int from,int to,int dis)
{
edge[++num_edge].next=head[from];
edge[num_edge].dis=dis;
edge[num_edge].to=to;
head[from]=num_edge;
}
inline int Dfs(int pos,int fth,int k)
{
multiset<int> S; S.clear();
for(int i=head[pos];i;i=edge[i].next)
if(edge[i].to!=fth)
{
int Bac=Dfs(edge[i].to,pos,k)+edge[i].dis;
if(Bac>=k) Ans++;
else S.insert(Bac);
}
int Max=0;
while(S.size())
{
if(S.size()==1) return max(Max,*S.begin());
multiset<int>::iterator It=S.lower_bound(k-*S.begin());
if(It==S.begin()&&S.count(*It)==1) It++;
if(It==S.end()) Max=max(Max,*S.begin()),S.erase(*S.begin());
else Ans++,S.erase(It),S.erase(S.begin());
}
return Max;
}
inline bool Check(int k)
{
Ans=0; Dfs(1,0,k);
if(Ans>=m) return 1;
else return 0;
}
inline void Dfs_For_Dia(int pos,int fth)
{
for(int i=head[pos];i;i=edge[i].next)
if(edge[i].to!=fth)
{
Dfs_For_Dia(edge[i].to,pos);
Sum=max(Sum,Dis[pos]+Dis[edge[i].to]+edge[i].dis);
Dis[pos]=max(Dis[pos],Dis[edge[i].to]+edge[i].dis);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
#endif
n=AE86::read(),m=AE86::read();
for(int i=1,U,V,D;i<n;i++)
U=AE86::read(),V=AE86::read(),D=AE86::read(),Add(U,V,D),Add(V,U,D);
Dfs_For_Dia(1,0);int l=0,r=Sum;
while(l<r)
{
int mid=(l+r+1)>>1;
if(Check(mid)) l=mid;
else r=mid-1;
}
printf("%d
",l);
}