#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define ii pair<ll, ll>
#define vii vector<ii>
#define pb push_back
#define mp make_pair
const ll mxN = 2e5+5, inf = 1e18;
ll n, k;
vii adj[mxN];
ll dis[mxN]; // dis de 0 a x
ll p[mxN];
map<ll, ll> dp[mxN]; // min len de path de peso x
void dfs(ll u = 0, ll par = -1, ll d = 0) {
p[u] = par;
dis[u] = d;
for (auto &[v, w] : adj[u]) {
if (v == par) continue;
dfs(v, u, d+w);
dp[u][w] = 1;
for (auto &[x, y] : dp[v]) {
if (w+d > k) break;
auto it = dp[u].find(x+w);
if (it == dp[u].end()) dp[u][x+w] = y+1;
else it->second = min(it->second, y+1);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for (ll i = 0; i < n-1; i++) {
ll x = H[i][0];
ll y = H[i][1];
adj[x].pb(mp(y, L[i]));
adj[y].pb(mp(x, L[i]));
}
dfs();
ll mn = inf;
for (ll i = 0; i < n; i++) {
auto it = dp[i].find(k);
if (it != dp[i].end()) {
mn = min(mn, it->second);
}
ll cnt = 1;
ll x = p[i];
ll son = i;
while (x != -1) {
for (auto &[v, w] : adj[x]) {
if (v == son || v == p[x]) continue;
ll d = dis[i] - dis[x] + w;
if (d >= k) break;
auto it2 = dp[v].find(k-d);
if (it2 != dp[v].end()) {
mn = min(mn, cnt+1 + it2->second);
}
}
son = x;
x = p[x];
cnt++;
}
}
return mn == inf ? -1 : mn;
}
