#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<int> dp(N), sum(N);
vector<bool> rem(N, false);
function<int(int, int)> dfs_sz = [&](int x, int p) {
int res = 1;
for (auto &[u, w] : adj[x]) {
if (u == p || rem[u]) continue;
res += dfs_sz(u, x);
}
return dp[x] = res;
};
function<int(int, int)> dfs_sum = [&](int x, int p) {
int res = 0;
for (auto &[u, w] : adj[x]) {
if (u == p || rem[u]) continue;
res += w + dfs_sum(u, x);
}
return res;
};
function<int(int, int, int)> centroid = [&](int x, int p, int sz) {
for (auto &[u, w] : adj[x]) {
if (u == p || rem[u]) continue;
if (dp[u] * 2 > sz) return centroid(u, x, sz);
}
return x;
};
int ans = INT_MAX;
function<void(int)> build = [&](int x) {
int cen = centroid(x, -1, dfs_sz(x, -1));
if (dfs_sum(cen, -1) < K) { rem[cen] = true; return; }
rem[cen] = true;
map<int, int> mn;
queue<tuple<int, int, int, int>> q;
mn[0] = 0;
for (auto &[u, w] : adj[cen]) {
if (rem[u]) continue;
map<int, int> nw;
nw[w] = 1;
q.emplace(u, cen, w, 1);
while (!q.empty()) {
auto [qu, qp, qw, ql] = q.front();
q.pop();
for (auto &[v, ww] : adj[qu]) {
if (v == qp || rem[v] || ww + qw > K) continue;
if (!nw.count(ww+qw)) nw[ww+qw] = ql;
else nw[ww+qw] = min(nw[ww+qw], ql);
}
}
for (auto &[len, val] : nw) {
if (!mn.count(K-len)) continue;
ans = min(ans, val + mn[K-len]);
}
for (auto &[len, val] : nw) {
if (!mn.count(len)) mn[len] = val;
mn[len] = min(mn[len], val);
}
}
for (auto &[u, w] : adj[cen]) {
if (rem[u]) continue;
build(u);
}
};
build(0);
return (ans == INT_MAX ? -1 : ans);
}
