#include "race.h"
#include <bits/stdc++.h>
using namespace std;
namespace std {
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template <class Fun>
class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
}; // namespace std
template <class T>
bool chmin(T& _old, T _new) { return _old > _new && (_old = _new, true); }
template <class T>
bool chmax(T& _old, T _new) { return _old < _new && (_old = _new, true); }
int best_path(int n, int k, int e[][2], int w[]) {
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < n - 1; ++i) {
adj[e[i][0]].emplace_back(w[i], e[i][1]);
adj[e[i][1]].emplace_back(w[i], e[i][0]);
}
vector<pair<int, int>> dists;
vector<int> sz(n), dist(n);
vector<bool> erased(n);
int s;
auto dfs_sz = y_combinator([&](auto self, int u, int p) -> int {
sz[u] = 1;
for (const auto& [w, v] : adj[u]) {
if (v != p && !erased[v]) {
sz[u] += self(v, u);
}
}
return sz[u];
});
auto dfs_ct = y_combinator([&](auto self, int u, int p) -> int {
for (const auto& [w, v] : adj[u]) {
if (v != p && !erased[v] && sz[v] > s / 2) {
return self(v, u);
}
}
return u;
});
auto dfs = y_combinator([&](auto self, int u, int p, int edges) -> void {
if (dist[u] > k) return;
dists.emplace_back(dist[u], edges);
for (const auto& [w, v] : adj[u]) {
if (v != p && !erased[v]) {
dist[v] = dist[u] + w;
self(v, u, edges + 1);
}
}
});
int ans = INT_MAX, tick = 0;
vector<pair<int, int>> table(k);
y_combinator([&](auto self, int u) -> void {
s = dfs_sz(u, -1);
u = dfs_ct(u, -1);
erased[u] = true;
--tick;
for (const auto& [w, v] : adj[u]) {
if (erased[v]) continue;
dists.clear();
dist[v] = w;
dfs(v, u, 1);
for (const auto& [d1, e1] : dists) {
if (d1 == k) {
chmin(ans, e1);
} else {
const auto d2 = k - d1;
if (table[d2].first == tick) {
chmin(ans, e1 + table[d2].second);
}
}
}
for (const auto& [d, e] : dists) {
if (d != k) {
chmin(table[d], pair(tick, e));
}
}
}
for (const auto& [w, v] : adj[u]) {
if (!erased[v]) {
self(v);
}
}
})(0);
return ans == INT_MAX ? -1 : ans;
}
