#include "race.h"
#include <bits/stdc++.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]);
}
vector<bool> vis(N);
vector<int> sz(N);
auto init = [&](auto init, int x, int p) -> void {
sz[x] = 1;
for (auto [y, _] : adj[x]) {
if (y == p || vis[y]) {
continue;
}
init(init, y, x);
sz[x] += sz[y];
}
};
auto find = [&](auto find, int x, int p, int s) -> int {
for (auto [y, _] : adj[x]) {
if (y == p || vis[y] || sz[y] * 2 <= s) {
continue;
}
return find(find, y, x, s);
}
return x;
};
int ans = N;
auto cd = [&](auto cd, int x) -> void {
init(init, x, -1);
x = find(find, x, -1, sz[x]);
vis[x] = 1;
map<int64_t, int> mp;
mp[0] = 0;
auto dfs = [&](auto dfs, int u, int p, int64_t len, int cnt, bool f) -> void {
if (f) {
if (!mp.count(len)) {
mp[len] = cnt;
} else {
mp[len] = min(mp[len], cnt);
}
} else {
if (mp.count(K - len)) {
ans = min(ans, mp[K - len] + cnt);
}
}
for (auto [v, w] : adj[u]) {
if (v != p && !vis[v]) {
dfs(dfs, v, u, len + w, cnt + 1, f);
}
}
};
for (auto [y, z] : adj[x]) {
if (vis[y]) {
continue;
}
dfs(dfs, y, x, z, 1, 0);
dfs(dfs, y, x, z, 1, 1);
cd(cd, y);
}
};
cd(cd, 0);
if (ans == N) {
ans = -1;
}
return ans;
}
