#include "race.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
int best_path(int N, int K, int H[][2], int L[]) {
std::vector<std::vector<std::pair<int, int>>> adj(N);
for (int i = 0; i + 1 < N; i++) {
int u = H[i][0], v = H[i][1], w = L[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
int ans = 1e9;
struct Answer {
int64_t dw = 0;
int dc = 0;
std::map<int64_t, int> mp;
int size() const {
return (int) mp.size();
}
};
auto merge = [&](Answer& l, Answer& r) {
if (l.size() < r.size()) std::swap(l, r);
for (auto [k, v] : r.mp) {
auto required = K - k - r.dw - l.dw; // all the added weight is loss
auto it = l.mp.find(required);
if (it != l.mp.end()) {
ans = std::min(ans, it->second + v + l.dc + r.dc);
}
// after that's done we merge
}
for (auto [k, v] : r.mp) {
auto nk = k + r.dw - l.dw;
auto nv = v + r.dc - l.dc;
auto it = l.mp.find(nk);
if (it == l.mp.end()) {
l.mp[nk] = nv;
} else {
it->second = std::min(it->second, nv);
}
}
};
auto dfs = [&](auto self, int u, int p) -> Answer {
Answer re;
re.mp[0] = 0;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
auto res = self(self, v, u);
res.dw += w;
res.dc++;
merge(re, res);
}
dbg(u, re.dc, re.dw, re.mp);
return re;
};
dfs(dfs, 0, 0);
return ans < 1e9 ? ans : -1;
}
