#include "race.h"
#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define wr cout << "/////////////////////////////" << endl
using namespace std;
const int INF = 1e9 + 7;
const int N = 2e5 + 5;
int sub[N];
bool removed[N];
vector<pair<int,int>>g[N];
map<int,int>cnt;
int ans = INF;
int k;
int fix_size(int nd,int p){
sub[nd] = 1;
for(auto [it,val]:g[nd])
if(it != p and !removed[it])
sub[nd] += fix_size(it,nd);
return sub[nd];
}
int search_centroid(int nd,int p,int lens){
for(auto [it,val]:g[nd])
if(it != p and !removed[it] and sub[it] > (lens >> 1))
return search_centroid(it,nd,lens);
return nd;
}
int find_centroid(int nd){
fix_size(nd,0);
return search_centroid(nd,0,sub[nd]);
}
void solve(int nd,int p,ll sum,int lvl){
if(sum > k)
return;
int need = k - sum;
// cout << nd << ' ' << p << ' ' << sum << ' ' << lvl << ' ' << cnt[need] << endl;
int res = cnt[need];
if(res)
ans = min(ans,res + lvl);
int kk = cnt[sum];
if(!kk or kk > lvl)
cnt[sum] = lvl;
for(auto [it,val]:g[nd])
if(it != p and !removed[it])
solve(it,nd,sum + val,lvl + 1);
}
void decompose(int nd){
int centroid = find_centroid(nd);
removed[centroid] = true;
for(auto [it,val]:g[centroid])
if(!removed[it])
solve(nd,centroid,val,1);
cnt.clear();
for(auto [it,val]:g[centroid])
if(!removed[it])
decompose(it);
}
int best_path(int n,int K,int h[][2],int l[]){
k = K;
for(int i = 0;i<n-1;++i)
g[h[i][0] + 1].pb({h[i][1] + 1,l[i]}), g[h[i][1] + 1].pb({h[i][0] + 1,l[i]});
decompose(1);
if(ans == INF)
ans = -1;
return ans;
}
