#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e5+10, MAXV=1e6+10;
vector<pair<int,int>>g[MAXV];
int n, k, centr, podd[MAXV], o[MAXV];
int odw[MAXV], wynik=MAXV, mini[MAXV];
void dfs(int v, int oj, int roz){
podd[v]=1, o[v]=oj;
int maxi=0;
for(auto s:g[v]){
if(s.fi!=oj && !odw[s.fi]){
dfs(s.fi, v, roz);
maxi=max(maxi, podd[s.fi]);
podd[v]+=podd[s.fi];
}
}
if(maxi<=roz/2 && (roz-podd[v])<=roz/2)
centr=v;
}
void zlicz(int v, int oj, int st, int akt, int ile){
if(akt>k) return;
wynik=min(wynik, mini[k-akt]+ile);
for(auto s:g[v]){
if(s.fi==oj||odw[s.fi]<=st) continue;
zlicz(s.fi, v, st, akt+s.se, ile+1);
}
}
void dodaj(int v, int oj, int st, int akt, int ile){
if(akt>k) return;
mini[akt]=min(mini[akt], ile);
for(auto s:g[v]){
if(s.fi==oj||odw[s.fi]<=st) continue;
dodaj(s.fi, v, st, akt+s.se, ile+1);
}
}
void zeruj(int v, int oj, int st, int akt, int ile){
if(akt>k) return;
mini[akt]=MAXV;
for(auto s:g[v]){
if(s.fi==oj||odw[s.fi]<=st) continue;
zeruj(s.fi, v, st, akt+s.se, ile+1);
}
}
void rek(int aktc, int roz, int st){
odw[aktc]=st;
for(auto s:g[aktc]){
if(!odw[s.fi]){
int newR=podd[s.fi];
if(s.fi==o[aktc]) newR=roz-podd[aktc];
centr=0;
dfs(s.fi, s.fi, newR);
rek(centr, newR, st+1);
}
}
mini[0]=0;
for(auto s: g[aktc]){
if(odw[s.fi]<=st) continue;
zlicz(s.fi, s.fi, st, s.se, 2);
dodaj(s.fi, s.fi, st, s.se, 1);
}
for(auto s: g[aktc]){
if(odw[s.fi]<=st) continue;
zeruj(s.fi, s.fi, st, s.se, 1);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N, k=K;
for(int i=0; i<n-1; i++)
g[H[i][0]].pb({H[i][1], L[i]}), g[H[i][1]].pb({H[i][0], L[i]});
for(int i=0; i<=k; i++)
mini[i]=MAXV;
dfs(0, 0, n);
rek(centr, n, 1);
if(wynik==MAXV) wynik=0;
return wynik-1;
}
