挺综合的一道题目。
询问最小值最大，考虑二分最小值，二分上下界是 \([最小边权,树的直径]\)，但是为了方便我们直接设为 \([1,5\times 10^8]\) 即可。
考虑如何 \(check\)，可以采用类似树形 \(dp\) 的方式进行贪心。对于节点 \(u\) 的子树，\(u\) 内部的点显然可以构成几条链，同时我们也可以从 \(u\) 内部引一条链出去，和上面的节点进行搭配，从而使得边权和大于我们二分的值。
问题也就转化为：将 \(u\) 的儿子尽可能的凑合，凑合出最多的链数量，然后从没有凑合好的链中选出一条最长的传上去，也就是说：在保证节点 \(u\) 内部的链数量最多，使得上传的权值最大。
对于节点 \(u\) 的儿子传上来的权值 \(val\)，若 \(val\ge mid\)，则直接计入贡献即可；反之先放到一边。
对于刚才不符合条件的 \(val\)，进行处理：由于要保证最终剩下来的最大，且一对搭配的贡献始终是 \(1\)，所以我们从小开始，查找与之搭配符合条件的，并选上，最终剩下的就是最大的。返回到父亲节点即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+10;
int n,m;
struct node {
int to,w;
};
vector<node> g[N];
void add(int x,int y,int z) {
g[x].push_back({y,z});
}
int sum=0;
LL dfs(int nd,int fa,LL s) {
multiset<LL> st,st2;
multiset<LL>::iterator it;
for(node t:g[nd]) {
int x=t.to,w=t.w;
if(x==fa) continue;
LL res=dfs(x,nd,s)+(LL)w;
if(res>=s) sum++;
else st.insert(res);
}
LL maxn=0;
while(st.size()>=2) {
LL minn=*st.begin(); st.erase(st.begin());
it=st.lower_bound(s-minn);
if(it==st.end()) { maxn=max(maxn,minn); continue; }
sum++;
st.erase(it);
}
if(st.size()) return max(maxn,*(--st.end()));
else return maxn;
}
int check(LL s) {
sum=0;
dfs(1,0,s);
if(sum>=m) return 1;
else return 0;
}
int main() {
cin>>n>>m;
for(int i=1;i<n;i++) {
int a,b,l; cin>>a>>b>>l;
add(a,b,l); add(b,a,l);
}
LL l=1,r=500000000;
while(l<r) {
LL mid=(l+r+(LL)1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}