前言
(STL) 毁我青春！！！
【题目传送门】
被折磨之后发的求助讨论：【讨论传送门】
题解
分析做法
二分答案显然，关键在于 check()。
根据每个节点 只有一个父亲，所以一旦某个节点选择向父亲选边，那么它的子树内的边都无法继续向上延伸，只能在子树内部消化了（在子树内部选出路径）。
根据贪心，如果在子树内能选出路径，就不需要考虑把这条路径保留，所以问题变为子树内的价值两两配对，最后剩下的价值最大值传递给父亲节点，可以用 set 或者 vector 实现。（set 应该复杂度更真一点）
特别地，如果一个节点本身的价值（相当于边权化点权）就已经足够当前二分的 (mid)，就直接 cnt++，不需要放入 set 里面。
一些问题
set的erase函数有返回值，返回值是删除元素的下一个位置，这样可以避免删除当前元素导致迭代器失效的问题。-
如果一个节点本身的价值（相当于边权化点权）就已经足够当前二分的 (mid)，就直接
cnt++，不需要放入set里面。
这个特判我一开始写在下面就 (WA) 了。
代码
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f,N = 5e4+10;
#define ll long long int
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int n,m;
int head[N],ecnt=-1;
struct edge
{
int nxt,to,w;
}a[N<<1];
void init_edge(){memset(head,-1,sizeof(head)),ecnt=-1;}
inline void add_edge(int x,int y,int w)
{
a[++ecnt]=(edge){head[x],y,w};
head[x]=ecnt;
}
int cnt,dp[N];
multiset<int> s[N];
multiset<int>::iterator it1,it2;
inline void clear()
{
memset(dp,0,sizeof(dp));
cnt=0;
}
void dfs(int u,int fa,int mid)
{
for(int i=head[u];~i;i=a[i].nxt)
{
int v=a[i].to;
if(v==fa) continue;
dfs(v,u,mid);
if(dp[v]+a[i].w>=mid) cnt++;//发现问题，必须在这里特判，不能在下面特判
else s[u].insert(dp[v]+a[i].w);
}
//printf("u=%d
",u);
for(it1=s[u].begin();it1!=s[u].end();)
{
// fprintf(stderr,"now=%d
",*it1);
if(s[u].empty()) break;
if(*it1>=mid)
{
it1=s[u].erase(it1);
cnt++;
continue;
}
if((signed)s[u].size()<2) break;
it2=s[u].lower_bound(mid-*it1);
if(it2==s[u].end()) {it1++;continue;}//找不到
if(it2==it1) it2++;//配对到自己，往后跳一个
if(it2==s[u].end()) {it1++;continue;}//只能找到自己（也是找不到）
// fprintf(stderr,"pair:(%d,%d)
",*it1,*it2);
it1=s[u].erase(it1);
if(it1==it2) it1=s[u].erase(it2),cnt++;
else s[u].erase(it2),cnt++;
if(it1==s[u].end()) break;
}
if(!s[u].empty())
{
it2=s[u].end(),it2--;
dp[u]=*it2;
s[u].clear();
}
}
bool check(int mid)
{
clear();
dfs(1,-1,mid);
return cnt>=m;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("build.in","r",stdin);
freopen("build.out","w",stdout);
#endif
init_edge();
n=read(),m=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read(),w=read();
add_edge(u,v,w),add_edge(v,u,w);
}
int l=1,r=1e9;
while(l<r)
{
int mid=(l+r+1)>>1;
// fprintf(stderr,"mid=%d--------------------
",mid);
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d
",l);
return 0;
}