#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> g;
int ans, k;
unordered_map<int, int> *dfs(int u, int p, int l, int d) {
vector sets = {new unordered_map{pair{l, d}}};
for (auto &[v, w] : g[u]) {
if (v == p) continue;
sets.push_back(dfs(v, u, l + w, d + 1));
}
auto ret = *max_element(sets.begin(), sets.end(), [](auto &a, auto &b) { return a->size() < b->size(); });
for (auto s : sets) {
if (ret == s) continue;
for (auto &x : *s) {
if (ret->count(k + 2 * l - x.first)) ans = min(ans, (*ret)[k + 2 * l - x.first] + x.second - 2 * d);
}
for (auto &x : *s) {
if (ret->count(x.first)) (*ret)[x.first] = min((*ret)[x.first], x.second);
else (*ret)[x.first] = x.second;
}
delete s;
}
return ret;
}
int best_path(int N, int K, int H[][2], int L[]) {
ans = 1e9;
k = K;
g.clear();
g.resize(N);
for (int i = 0; i < N - 1; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
delete dfs(0, 0, 0, 0);
return ans == 1e9 ? -1 : ans;
}
