#include "race.h"
#include <bits/stdc++.h>
using LL = long long;
const LL INF = 1e9;
using namespace std;
using pii = pair<LL, LL>;
#define pb push_back
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
int best_path(int N, int K, int H[][2], int L[]) {
LL ans = INF;
vector e(N, vector<pii>());
for (LL i = 0; i < N - 1; i++) {
LL x = H[i][0], y = H[i][1], d = L[i];
e[x].pb({y, d});
e[y].pb({x, d});
}
//debug(e);
vector<bool> v(N);
vector<LL> sub(N);
auto cen_decomp = [&](auto cen_decomp, LL g, LL SZ) -> void {
auto dfs_sub = [&](auto dfs_sub, LL g, LL p) -> void {
sub[g] = 1;
for (auto [u, d] : e[g]) if (u != p && !v[u]) {
dfs_sub(dfs_sub, u, g);
sub[g] += sub[u];
}
};
auto find_cen = [&](auto find_cen, LL g, LL p) -> LL {
for (auto [u, d] : e[g]) if (u != p && !v[u]) {
if (sub[u] * 2 >= SZ)
return find_cen(find_cen, u, g);
}
return g;
};
dfs_sub(dfs_sub, g, -1);
g = find_cen(find_cen, g, -1);
dfs_sub(dfs_sub, g, -1);
//debug(g);
v[g] = 1;
map<LL, LL> dp;
auto fill_dp = [&](auto fill_dp, LL g, LL p, LL L, LL d) -> void {
if (!dp.count(L)) {
dp[L] = d;
} else {
dp[L] = min(dp[L], (LL)d);
}
for (auto [u, nl] : e[g]) if (!v[u] && u != p) {
fill_dp(fill_dp, u, g, L + nl, d + 1);
}
};
auto compare_dp = [&](auto compare_dp, LL g, LL p, LL L, LL d) -> void {
if (dp.count(K - L)) {
ans = min(ans, d + dp[K - L]);
}
for (auto [u, nl] : e[g]) if (!v[u] && u != p) {
compare_dp(compare_dp, u, g, L + nl, d + 1);
}
};
dp[0] = 0;
for (auto [u, d] : e[g]) if (!v[u]) {
compare_dp(compare_dp, u, g, d, 1);
fill_dp(fill_dp, u, g, d, 1);
}
for (auto [u, d] : e[g]) if (!v[u]) {
cen_decomp(cen_decomp, u, sub[u]);
}
};
cen_decomp(cen_decomp, 0, N);
return (ans >= INF ? -1 : ans);
}
