观察题目不难想到二分答案。
考虑二分所有赛道的最小长度值，那么我们可以去判断最后修建出来的赛道数是不是大于等于 \(m\) 条即可。
用 \(f_{i}\) 表示当前以 \(i\) 为根，最长的未被赛道占用的链的长度。
但是有很多链，匹配的过程不好进行，所以改为用 multiset 来维护当前点的链有多少个没匹配的。
在处理完所有子树后，对 mltiset 内的元素分以下几种情况讨论：
-
当前
set内只有一个元素，直接退出，当前点最长未匹配的就是他。 -
当前
set内有多个，那么取最小值，然后看set里是否有元素和他加起来能到mid，如果可以就sum++，反之删除，然后更新最大未匹配的链长。 -
有一个特殊情况就是当前单条链就大于等于
mid了，可以直接不加进set里。
/*
* @Author: Aisaka_Taiga
* @Date: 2023-10-29 15:17:24
* @LastEditTime: 2023-10-29 16:27:11
* @LastEditors: Aisaka_Taiga
* @FilePath: \Desktop\P5021.cpp
* The heart is higher than the sky, and life is thinner than paper.
*/
#include <bits/stdc++.h>
#define int long long
#define N 50100
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '0') f = -1; c = getchar();}
while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x * f;
}
int n, m, head[N << 1], cnt, ans, sum, mid;
struct node{int u, v, w, next;}e[N << 1];
multiset<int> s[N];
multiset<int> :: iterator it;
inline void add(int u, int v, int w){e[++ cnt] = (node){u, v, w, head[u]}; head[u] = cnt;}
inline int dfs(int x, int fa)
{
s[x].clear();//每次都清空一下
for(int i = head[x]; i; i = e[i].next)
{
int v = e[i].v;
if(v == fa) continue;
int val = e[i].w + dfs(v, x);//当前子树通过这条道路能到x点的长度
if(val >= mid) sum ++;//直接大于mid了就归成一条赛道，条数加1
else s[x].insert(val);//否则就插入当前点的set里
}
int res = 0;//存放当前点能到达x点的最短的路径长度
while(!s[x].empty())
{
if(s[x].size() == 1) return max(res, *s[x].begin());//只有一个就没有可以选的直接返回第一个
int kk = *s[x].begin();//当前最小的元素的值
s[x].erase(s[x].begin());//删除
it = s[x].lower_bound(mid - kk);//找到当前子树里最小的差多少
if(it == s[x].end()) res = max(res, kk);//找不到加起来能到mid的就更新没匹配的最大值
else sum ++, s[x].erase(it);//能匹配上就赛道数+1，删除当前的长度
}
return res;
}
inline int check()
{
sum = 0;//存放当前mid长度能分出来的赛道条数
dfs(1, 0);
return sum >= m;
}
signed main()
{
n = read(), m = read();
for(int i = 1; i <= n - 1; i ++)
{
int u = read(), v = read(), w = read();
add(u, v, w), add(v, u, w);
}
int l = 1, r = 1e9;
while(l < r)
{
mid = (l + r) >> 1;
if(check()) l = mid + 1;
else r = mid;
}
cout << l - 1 << endl;
return 0;
}
/*
7 1
1 2 10
1 3 5
2 4 9
2 5 8
3 6 6
3 7 7
*/