#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 (auto i = 0; i < N - 1; ++i) {
auto u = H[i][0];
auto v = H[i][1];
adj[u].emplace_back(v, L[i]);
adj[v].emplace_back(u, L[i]);
}
constexpr auto inf = numeric_limits<int>::max() / 2;
vector<int> subtree_size(N), r(K + 1, inf);
vector<bool> done(N);
r[0] = 0;
auto ans = inf;
auto dfs_size = [&](auto self, int u, int p) -> int {
auto &ret = subtree_size[u];
ret = 1;
for (auto [v, w] : adj[u]) {
if (v != p && !done[v]) {
ret += self(self, v, u);
}
}
return ret;
};
auto dfs_centroid = [&](auto self, int u, int p, int sz) -> int {
for (auto [v, w] : adj[u]) {
if (v != p && !done[v] && sz / 2 < subtree_size[v]) {
return self(self, v, u, sz);
}
}
return u;
};
auto dfs = [&](auto self, int u, int p, int d, int cnt, auto f) -> void {
if (K < d) {
return;
}
f(d, cnt);
for (auto [v, w] : adj[u]) {
if (v != p && !done[v]) {
self(self, v, u, d + w, cnt + 1, f);
}
}
};
auto centroid_decomposition = [&](auto self, int u) -> void {
auto sz = dfs_size(dfs_size, u, u);
u = dfs_centroid(dfs_centroid, u, u, sz);
done[u] = true;
for (auto [v, w] : adj[u]) {
if (!done[v]) {
dfs(dfs, v, u, w, 1,
[&](int d, int cnt) { ans = min(ans, r[K - d] + cnt); });
dfs(dfs, v, u, w, 1,
[&](int d, int cnt) { r[d] = min(r[d], cnt); });
}
}
for (auto [v, w] : adj[u]) {
if (!done[v]) {
dfs(dfs, v, u, w, 1,
[&](int d, [[maybe_unused]] int cnt) { r[d] = inf; });
}
}
for (auto [v, w] : adj[u]) {
if (!done[v]) {
self(self, v);
}
}
};
centroid_decomposition(centroid_decomposition, 0);
if (ans == inf) {
ans = -1;
}
return ans;
}
