#include<bits/stdc++.h>
#include "race.h"
#define ll long long
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int sz = 2e5+5;
const ll inf = 1000000000000000;
bool used[sz];
vector<pair<ll,ll>> arr, adj[sz];
ll n, k, ss[sz], res = inf;
map<ll,ll> mp;
void construct(ll node, ll p){
ss[node] = 1;
for(pair<ll,ll> edge: adj[node]){
if(!used[edge.fi] && edge.fi != p){
construct(edge.fi, node);
ss[node] += ss[edge.fi];
}
}
}
ll centroid(ll v, ll p, ll cs){
for(pair<ll,ll> edge: adj[v]){
if(edge.fi == p || used[edge.fi]){continue;}
if(ss[edge.fi] > (cs>>1)){
return centroid(edge.fi, v, cs);
}
}
return v;
}
void init(ll v, ll p, ll w, ll we){
if(mp.find(k - w) != mp.end()){
res = min(res, mp[k-w] + we);
}
arr.pb({w, we});
for(pair<ll,ll> edge: adj[v]){
if(used[v] || edge.fi == p){continue;}
init(edge.fi, v, w + edge.se, we + 1);
}
}
void calc(ll node){
mp.clear();
construct(node, -1);
ll c = centroid(node, -1, ss[node]);
mp[0] = 0;
for(pair<ll,ll> edge: adj[c]){
if(used[edge.fi]){continue;}
arr.clear();
init(edge.fi, c, edge.se, 1);
for(pair<ll,ll> y: arr){
if(mp.find(y.fi) == mp.end()){
mp[y.fi] = y.se;
}
else{
mp[y.fi] = min(mp[y.fi], y.se);
}
}
}
used[c] = 1;
for(pair<ll,ll> edge: adj[c]){
if(!used[edge.fi]){
calc(edge.fi);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for(ll i=0;i<n-1;i++){
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
calc(0);
if(res == inf){
return -1;
}
return res;
}
