#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int best_path(int n, int k, int H[][2], int L[]) {
vector<vector<pair<ll, ll>>> adj(n);
for (int i = 0; i < n-1; i++) {
ll u = H[i][0], v = H[i][1], w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
ll ans = 1e18;
vector<map<ll, ll>> mp(n); // [dist from root, cost]
auto dfs = [&](auto dfs, int u = 0, int p = 0, int d = 0, ll dw = 0) -> void {
for (auto [v, w] : adj[u]) if (v != p) {
dfs(dfs, v, u, d+1, dw+w);
if (mp[v].size() > mp[u].size()) mp[u].swap(mp[v]);
for (auto [dw2, d2] : mp[v]) {
// dw2+dw3-2*dw = k
// dw3 = k-dw2+2*dw
ll need = k+2*dw-dw2;
if (mp[u].count(need)) ans = min(ans, d2+mp[u][need]-2*d+1);
}
for (auto [dw2, d2] : mp[v]) {
if (mp[u].count(dw2)) mp[u][dw2] = min(mp[u][dw2], d2);
else mp[u][dw2] = d2;
}
}
ll need = k+dw;
if (mp[u].count(need)) ans = min(ans, mp[u][need]-d);
mp[u][dw] = d;
//cout << u << ": " << endl;
//for (auto [x, y] : mp[u]) cout << "\t" << x << " " << y << endl; cout << endl;
};
dfs(dfs);
return ans == 1e18 ? -1 : ans;
}
