#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
const int mxN = 2e5 + 5;
vector<pair<int, ll>> adj[mxN];
multiset<pair<ll, int>> s[mxN];
int K;
int dfs(int v, int fa) {
s[v].insert({0, 0}); // Path of length 0 with 0 edges from v
int min_edges = 1e9;
for (auto [u, w] : adj[v]) {
if (u == fa) continue;
int child_min = dfs(u, v);
// Paths entirely within u's subtree
min_edges = min(min_edges, child_min);
// Paths from v through u
vector<pair<ll, int>> new_paths;
for (auto [len, cnt] : s[u]) {
ll new_len = len + w;
int new_cnt = cnt + 1;
if (new_len == K) {
min_edges = min(min_edges, new_cnt);
} else if (new_len < K) {
new_paths.push_back({new_len, new_cnt});
}
}
// Paths combining s[v] and s[u] through v
for (auto [len1, cnt1] : s[u]) {
ll need = K - w - len1;
if (need < 0) continue;
auto it = s[v].lower_bound({need, 0});
if (it != s[v].end() && it->ff == need) {
min_edges = min(min_edges, cnt1 + it->ss + 1);
}
}
// Merge u's paths into v
for (auto p : new_paths) {
s[v].insert(p);
}
}
return min_edges == 1e9 ? 1e9 : min_edges;
}
int best_path(int N, int K, int H[][2], int L[]) {
::K = K;
for (int i = 0; i < N; i++) {
adj[i].clear();
s[i].clear();
}
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
int result = dfs(0, -1);
return result == 1e9 ? -1 : result;
}
