/*
dp[i]表示孤立i结点的费用，二分功率上限w，即dp[i]在选择时不可以选择功率大于w的边
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 1050
struct Edge{
int to,nxt,w;}edge[maxn<<
1];
int x,flag[maxn],dp[maxn],tot,head[maxn],n,m;
void init(){
tot=
0;
memset(head,-
1,
sizeof head);
}
void addedge(
int u,
int v,
int w){
edge[tot].to=v;edge[tot].nxt=head[u];edge[tot].w=w;head[u]=tot++
;
}
int dfs(
int u,
int pre){
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=edge[i].to,tmp=
edge[i].w;
if(tmp>x)tmp=
1100000;
if(v==pre)
continue;
if(flag[v]==
0)dp[u]+=tmp;
//叶子结点
else dp[u]+=
min(tmp,dfs(v,u));
}
return dp[u];
}
int judge(
int mid){
x=
mid;
memset(dp,0,
sizeof dp);
dfs(1,
0);
if(dp[
1]>m)
return 0;
return 1;
}
int main(){
while(cin>>n>>m&&
n){
init();
int u,v,w,l=
1000000,r=
1,mid,ans=-
1;
memset(flag,0,
sizeof flag);
for(
int i=
1;i<n;i++
){
cin>>u>>v>>
w;
addedge(u,v,w);
addedge(v,u,w);
flag[u]=
1;
l=min(l,w);r=
max(r,w);
}
while(l<=
r){
mid=l+r>>
1;
if(judge(mid))
ans=mid,r=mid-
1;
else l=mid+
1;
}
printf("%d\n",ans);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10341331.html
