#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <map>
using namespace std;
using ll = long long;
const int maxn=2e5+10;
vector<pair<ll,int>> g[maxn];
bool alive[maxn];
int siz[maxn];
int dfs(int at, int p) {
siz[at] = 1;
for (auto ed: g[at]) {
int to = ed.second;
if (to==p) continue;
if (!alive[to]) continue;
siz[at] += dfs(to, at);
}
return siz[at];
}
void dfs2(int at, int p, int ¢roid, int cnt) {
int hi = 0;
for (auto ed: g[at]) {
int to = ed.second;
if (to==p) continue;
if (!alive[to]) continue;
dfs2(to,at,centroid,cnt);
hi = max(hi, siz[to]);
}
hi = max(hi, cnt-siz[at]);
//cout<<at<<": hi: "<<hi<<endl;
if (hi+hi<=cnt) centroid=at;
}
int ans;
// dp[sum] = min_length
map<ll,int> solve(int at, ll k, int n) {
dfs(at,at);
int cnt = siz[at];
int centroid = -1;
dfs2(at,at,centroid,cnt);
assert(~centroid);
//cout<<at<<":--> "<<centroid<<endl;
at = centroid;
alive[at] = false;
map<ll,int> dp;
for (auto ed: g[at]) {
int to = ed.second;
if (alive[to]) {
auto rec = solve(to, k, n);
for (auto p: rec) {
ll wei = ed.first + p.first;
int len = p.second;
if (dp.count(k-wei)) {
ans = min(ans, len+1+dp[k-wei]);
}
}
for (auto p: rec) {
ll wei = ed.first + p.first;
int len = p.second;
if (!dp.count(wei)) dp[wei]=n;
dp[wei] = min(dp[wei], len+1);
}
}
}
dp[0] = 0;
// cout<<"at: "<<at<<endl;
// for (auto p: dp) cout<<p.first<<": "<<p.second<<endl;
return dp;
}
int best_path(int n, int k, int H[][2], int L[]) {
for (int i=0; i<n-1; i++) {
int u=H[i][0];
int v=H[i][1];
int w=L[i];
g[v].push_back({w,u});
g[u].push_back({w,v});
}
for (int i=0; i<n; i++) {
alive[i]=true;
}
ans = n;
solve(0,k,n);
if (ans == n) ans = -1;
return ans;
}
