#include <iostream>
#include <vector>
#include "race.h"
using namespace std;
const int N1=2e5+1;
const int K1=101;
const int inf=1e6;
int ans=inf,wnt;
vector<pair<int,int>> ma[N1];
int dp_up[N1][K1];
int dp_down[N1][K1][2];
void dfs_down(int x,int p=-1)
{
dp_down[x][0][0]=dp_down[x][0][1]=0;
for(auto [y,w]:ma[x])
{
if(y!=p)
{
dfs_down(y,x);
for(int kp=0;(kp+w)<=wnt;kp++)
{
if(dp_down[x][kp+w][0]>(1+dp_down[y][kp][0]))
{
dp_down[x][kp+w][1]=dp_down[x][kp+w][0];
dp_down[x][kp+w][0]=dp_down[y][kp][0]+1;
}
else if(dp_down[x][kp+w][1]>(1+dp_down[y][kp][0]))
{
dp_down[x][kp+w][1]=dp_down[y][kp][0]+1;
}
}
}
}
}
void dfs_up(int x,int p=-1)
{
for(auto [y,w]:ma[x])
{
if(y!=p)
{
for(int kp=0;(kp+w)<=wnt;kp++)
{
dp_up[y][kp+w]=dp_up[x][kp]+1;
if((kp-(w))>=0 and dp_down[x][kp][0]==(dp_down[y][kp-w][0]+1))
{
dp_up[y][kp+w]=min(dp_up[y][kp+w],dp_down[x][kp][1]+1);
}
else
{
dp_up[y][kp+w]=min(dp_up[y][kp+w],dp_down[x][kp][0]+1);
}
}
dfs_up(y,x);
}
}
}
void dfs(int x,int p=-1,long long su=0,int h=0)
{
if(su==wnt)
ans=min(ans,h);
for(auto [y,w]:ma[x])
if(y!=p)
dfs(y,x,(su+w),h+1);
}
int best_path(int n, int k, int h[][2], int l[])
{
wnt=k;
for(int i=0;i<(n-1);i++)
{
ma[h[i][0]].push_back({h[i][1],l[i]});
ma[h[i][1]].push_back({h[i][0],l[i]});
}
if(n<=1000)
{
for(int i=0;i<n;i++)
dfs(i);
if(ans==inf)
ans=-1;
return ans;
}
else
{
for(int i=0;i<n;i++)
for(int j=1;j<=k;j++)
dp_down[i][j][0]=dp_down[i][j][1]=dp_up[i][j]=inf;
dfs_down(0);
dfs_up(0);
for(int i=0;i<n;i++)
{
ans=min(ans,dp_down[i][k][0]);
ans=min(ans,dp_up[i][k]);
}
if(ans==inf)
ans=-1;
return ans;
}
return -1;
}
