#include "race.h"
#include <vector>
#include <map>
#include <functional>
using namespace std;
#define pb push_back
typedef pair<int,int> pi;
const int inf = 1e9;
int best_path(int N, int K, int H[][2], int L[]) {
vector<pi> adj[N];
for (int i = 0; i < N - 1; i++) {
int u = H[i][0], v = H[i][1], w = L[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
vector<long long> path(N);
vector<int> dep(N);
vector<vector<pi>> pres(N); // (path_dist, depth)
int ans = inf;
function<void(int, int, map<long long, int>&)> dfs = [&](int u, int p, map<long long, int>& mp) {
mp[path[u]] = dep[u];
pres[u].emplace_back(path[u], dep[u]);
for (auto [v, w] : adj[u]) {
if (v == p) continue;
path[v] = path[u] + w;
dep[v] = dep[u] + 1;
map<long long, int> curr;
dfs(v, u, curr);
// small-to-large: keep larger in pres[u]/mp
if ((int)pres[u].size() < (int)pres[v].size()) {
swap(pres[u], pres[v]);
swap(mp, curr);
}
// check pairs across the merge
for (auto [x, d] : pres[v]) {
long long need = 2LL * path[u] + K - x;
auto it = mp.find(need);
if (it == mp.end()) continue;
ans = min(ans, it->second + d - 2 * dep[u]);
}
// merge pres[v] into pres[u] and mp
for (auto [x, d] : pres[v]) {
pres[u].emplace_back(x, d);
auto it = mp.find(x);
if (it != mp.end())
it->second = min(it->second, d);
else
mp[x] = d;
}
}
};
map<long long, int> tmp;
dfs(0, -1, tmp);
return ans == inf ? -1 : ans;
}
