#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int best_path(int n, int k, int h[][2], int l[]) {
vector<vector<pair<int, int>>> v(n);
for (int i = 0; i < n - 1; i++) {
int a = h[i][0], b = h[i][1], c = l[i];
v[a].push_back({b, c});
v[b].push_back({a, c});
}
int tim = -1;
vector<int> sz(n), big(n, -1), tin(n), tout(n), idx(n), dep(n);
vector<long long> d(n);
function<void(int, int)> dfs = [&](int x, int p) {
sz[x] = 1;
tin[x] = ++tim;
idx[tim] = x;
for (auto [z, c] : v[x]) {
if (z == p) continue;
d[z] = d[x] + c;
dep[z] = dep[x] + 1;
dfs(z, x);
sz[x] += sz[z];
if (big[x] == -1 || sz[z] > sz[big[x]]) big[x] = z;
}
tout[x] = tim;
};
dfs(0, 0);
int ans = INF;
map<long long, int> mp;
function<void(int, int, bool)> solve = [&](int x, int p, bool del) {
for (auto [z, c] : v[x]) {
if (z == p || z == big[x]) continue;
solve(z, x, 1);
}
if (big[x] != -1) solve(big[x], x, 0);
for (auto [z, c] : v[x]) {
if (z == p || z == big[x]) continue;
for (int tim = tin[z]; tim <= tout[z]; tim++) {
int z = idx[tim];
if (mp.count(d[x] + k - (d[z] - d[x]))) ans = min(ans, mp[d[x] + k - (d[z] - d[x])] + dep[z] - 2 * dep[x]);
}
for (int tim = tin[z]; tim <= tout[z]; tim++) {
int z = idx[tim];
if (!mp.count(d[z])) mp.insert({d[z], dep[z]});
else mp[d[z]] = min(mp[d[z]], dep[z]);
}
}
if (mp.count(d[x] + k)) ans = min(ans, mp[d[x] + k] - dep[x]);
if (!mp.count(d[x])) mp.insert({d[x], dep[x]});
else mp[d[x]] = min(mp[d[x]], dep[x]);
if (del) mp.clear();
};
solve(0, 0, 0);
if (ans == INF) ans = -1;
return ans;
}
