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