考场上把暴力都打满了，结果文件输入输出写错了....
当时时间很充裕，如果认真想想正解是可以想出来的..
问你 长度最小的赛道长度的最大值
显然二分答案
考虑如何判断是否可行
显然对于一个节点，它最多只能向父亲传一条路径长度
那么其它路径的合并只能在子树间进行
贪心一波，如果一段路径在子树就可以合并出合法长度
那么直接合并一定是不会比传给父亲再考虑合并更劣的
子树都合并完后，剩下的肯定传最长的长度给父亲
考虑在子树内如何贪心地进行最优合并
显然最小的边去找最小的能使它合法的边合并
（注意不是最大的边去找最小的能使它合法的边合并）
那么用一个multiset存一下当前节点的各个边长
然后就按前面的方法一个个合并就好了
注意和并时的一些细节和二分的上界，（因为multiset常数大，所以要把上界设为总长除赛道数）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
const int N=1e5+,INF=2e9+;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
int fir[N],from[N<<],to[N<<],val[N<<],cntt;
inline void add(int &a,int &b,int &c)
{
from[++cntt]=fir[a];
fir[a]=cntt; to[cntt]=b; val[cntt]=c;
}
int n,m,mid,cnt;
int f[N];
multiset <int> S;
multiset <int>::iterator it,itt,pit;
void dfs(int x,int fa)
{
for(int i=fir[x];i;i=from[i])
{
int &v=to[i]; if(fa==v) continue;
dfs(v,x);//先把每个节点遍历一波再从后往前更新会比较方便(不然要开一堆set)
}
S.clear();//记得清空
for(int i=fir[x];i;i=from[i])
{
int &v=to[i]; if(fa==v) continue;
if(f[v]+val[i]>=mid) cnt++;//只考虑小于mid的长度的合并(大于的不用合并都有贡献)
else S.insert(f[v]+val[i]);//注意把儿子传的边长加上父子间的边长
}
it=S.begin();
while(it!=S.end())
{
itt=S.lower_bound(mid-(*it));
if(itt==it) itt++;//注意细节
if(itt!=S.end()) cnt++,S.erase(itt),pit=it,it++,S.erase(pit);
else it++;
}
f[x]=;/*记得先清空f*/ it=S.begin(); if(S.end()!=it) it=S.end(),it--,f[x]=*it;//注意必须有边传才更新f
} inline int judge()
{
cnt=; dfs(,);
return cnt>=m;
} int main()
{
int a,b,c,s=;
n=read(); m=read();
for(int i=;i<n;i++)
{
a=read(); b=read(); c=read();
add(a,b,c); add(b,a,c); s+=c;
}
int L=,R=s/m;
while(R-L>)
{
mid=L+R>>;
if(judge()) L=mid; else R=mid;
}
mid=R;
printf("%d",judge() ? R : L);
return ;
}