#include <bits/stdc++.h>
#include "race.h"
using namespace std;
int best_path(int N, int K, int H[][2], int L[]) {
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < N - 1; ++i) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
int ans = N;
vector<int> pr(N), sz(N), subtree(N);
vector<bool> visit(N);
function<void(int, int)> centroid_decomposition = [&](int x, int s) {
int root = -1;
pr[x] = -1;
function<void(int)> find_root = [&](int x) {
subtree[x] = 0;
sz[x] = 1;
for (auto p : adj[x]) {
int y = p.first;
if (!visit[y] && y != pr[x]) {
pr[y] = x;
find_root(y);
sz[x] += sz[y];
subtree[x] = max(subtree[x], sz[y]);
}
}
subtree[x] = max(subtree[x], s - sz[x]);
if (root == -1 || subtree[x] < subtree[root]) {
root = x;
}
};
find_root(x);
visit[x = root] = true;
if (pr[x] != -1) {
sz[pr[x]] = s - sz[x];
}
pr[x] = -1;
unordered_map<int, int> f;
f[0] = 0;
function<void(int, int, int)> query = [&](int x, int d, int v) {
if (v > K) {
return;
}
if (f.count(K - v)) {
ans = min(ans, f[K - v] + d);
}
for (auto p : adj[x]) {
int y = p.first, w = p.second;
if (!visit[y] && y != pr[x]) {
pr[y] = x;
query(y, d + 1, v + w);
}
}
};
function<void(int, int, int)> modify = [&](int x, int d, int v) {
if (v > K) {
return;
}
if (f.count(v)) {
f[v] = min(f[v], d);
} else {
f[v] = d;
}
for (auto p : adj[x]) {
int y = p.first, w = p.second;
if (!visit[y] && y != pr[x]) {
pr[y] = x;
modify(y, d + 1, v + w);
}
}
};
for (auto p : adj[x]) {
int y = p.first, w = p.second;
if (!visit[y]) {
pr[y] = x;
query(y, 1, w);
modify(y, 1, w);
}
}
for (auto p : adj[x]) {
int y = p.first;
if (!visit[y]) {
centroid_decomposition(y, sz[y]);
}
}
};
centroid_decomposition(0, N);
if (ans == N) {
ans = -1;
}
return ans;
}
