@[Anguei](/space/show?uid=53062)
by Leap_Frog @ 2019-06-22 11:15:44
呃
by momentous @ 2019-06-22 11:26:03
@[chen_zhe](/space/show?uid=8457)
by momentous @ 2019-06-22 11:27:07
用
vector
by 洛谷亿亿岁 @ 2019-06-22 11:30:38
```cpp
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;int cc=0;
int head[50010],next[100010],to[100010],w[100010];
multiset<int>ss[100010];
multiset<int>::iterator it;//multiset的指针声明
void add(int u,int v,int ww)
{
to[++cc]=v;
next[cc]=head[u];
head[u]=cc;
w[cc]=ww;
}
int n,m,sum;
int dfs(int u,int fa,int pp)
{
ss[u].clear();
int val;
for(int i=head[u];i;i=next[i])
{
int v=to[i];
if(v==fa)continue;
val=dfs(v,u,pp)+w[i];
//val为
//经过v节点的，未能成为赛道的最长的路段
if(val>=pp)sum--;
else ss[u].insert(val);
}
int Max=0;
while(ss[u].empty()==0)
{
if(ss[u].size()==1)
{
return max(Max,*ss[u].begin());
}
it=ss[u].lower_bound(pp-*ss[u].begin());
if(it==ss[u].begin()&&ss[u].count(*it)==1)it++;
if(it==ss[u].end())//如果不存在值
{
Max=max(Max,*ss[u].begin());
ss[u].erase(ss[u].find(*ss[u].begin()));
}
else
{
sum--;
ss[u].erase(ss[u].find(*ss[u].begin()));
ss[u].erase(ss[u].find(*it));
}
}
return Max;
}
bool check(int x)
{
sum=m;
dfs(1,0,x);
return sum<=0;
}
signed main()
{
//freopen("testdata.in","r",stdin);
scanf("%d%d",&n,&m);
int l=0,r=0;
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
r+=z;
}
int ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
printf("%d",ans);
return 0;
}
```
by GLZP @ 2019-09-18 11:03:37
@[momentous](/user/42714) %%%
by RainFestival @ 2022-01-11 10:44:47