#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, inf = 2e9;
int n, k, d2;
vii adj[mxN];
int dis[mxN]; // dis de 1 a x
int p[mxN];
unordered_set<int> dp[mxN]; // min len de path de peso x
void dfs(int u = 0, int par = -1) {
p[u] = par;
for (auto &[v, w] : adj[u]) {
if (v == par) continue;
dis[v] = dis[u]+w;
dfs(v, u);
if (w <= k && w) dp[u].insert(w);
for (auto x : dp[v]) {
if (x+w > k || !x) continue;
//if (x+w > k) break;
//if (!x) continue;
dp[u].insert(x+w);
}
}
}
void findPath(int u, int par, int d) {
if (d == 0) return;
for (auto &[v, w] : adj[u]) {
if (v == par || (d-w != 0 && dp[v].find(d-w) == dp[v].end())) continue;
d2++;
findPath(v, u, d-w);
}
}
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]));
}
dis[0] = 0;
dfs();
int mn = inf;
for (int i = 0; i < n; i++) {
auto it = dp[i].find(k);
if (it != dp[i].end()) {
d2 = 0;
findPath(i, p[i], k);
mn = min(mn, d2);
}
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;
if (k == d) {
mn = min(mn, cnt+1);
continue;
}
auto it2 = dp[v].find(k-d);
if (it2 != dp[v].end()) {
d2 = 0;
findPath(v, p[v], k-d);
mn = min(mn, cnt+1 + d2);
}
}
son = x;
x = p[x];
cnt++;
}
}
return mn == inf ? -1 : mn;
}
