#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define int long long
const int N = 1e6+1, inf = 1e9+1;
vector <vector<pair<int,int>>> g;
map <int,int> cnt;
int sub[N], used[N], K, res;
void get_size(int x, int par){
sub[x] = 1;
for ( auto [to, w]: g[x] ){
if ( used[to] or to == par ) continue;
get_size(to, x);
sub[x] += sub[to];
}
}
int get_ctr(int x, int par, int desired){
for ( auto [to, w]: g[x] ){
if ( used[to] or to == par ) continue;
if ( desired <= sub[to] ) return get_ctr(to, x, desired);
}
return x;
}
void dfs(int x, int par, int depth, int len, bool add){
if ( len > K ) return;
if ( !add ){
if ( len == K ) res = min(res, depth);
else res = min(res, !cnt.count(K-len) ? inf : cnt[K-len]+depth);
}
else{
if ( !cnt.count(len) ) cnt[len] = depth;
else cnt[len] = min(cnt[len], depth);
}
for ( auto [to, w]: g[x] ){
if ( used[to] or to == par ) continue;
dfs(to, x, depth+1, len+w, add);
}
}
void ctr_dec(int x){
get_size(x, -1);
int cur = get_ctr(x, -1, sub[x]/2);
cnt.clear();
used[cur] = true;
for ( auto [to, w]: g[cur] ){
if ( used[to] ) continue;
dfs(to, -1, 1, w, false);
dfs(to, -1, 1, w, true);
}
for ( auto [to, w]: g[cur] ){
if ( used[to] ) continue;
ctr_dec(to);
}
}
int best_path(int n, int k, int h[][2], int L[]){
g.resize(n);
for ( int i = 0; i+1 < n; i++ ){
g[h[i][0]].pb({h[i][1], L[i]});
g[h[i][1]].pb({h[i][0], L[i]});
}
K = k; res = inf;
ctr_dec(0);
if ( res == inf ) res = -1;
return res;
}
