#include "race.h"
#include <functional>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int best_path(int N, int K, int H[][2], int L[]) {
vector <vector <pair <int, int> > > gr (N);
for (int i = 0; i < N - 1; i++) {
gr[H[i][0]].emplace_back (H[i][1], L[i]);
gr[H[i][1]].emplace_back (H[i][0], L[i]);
}
vector <bool> dis (N + 1);
vector <int> down_sum (N + 1);
vector <pair <int, int> > can (K + 1, {0, -1});
int ans = 2e9;
int step = 1;
auto f = [&](auto& f, int stp)->void {
step++;
vector <int> points;
auto dfs1 = [&](auto& dfs1, int p, int par)->void {
down_sum[p] = 1;
points.emplace_back (p);
for (pair <int, int>& e : gr[p])
if (e.first != par && !dis[e.first]) {
dfs1 (dfs1, e.first, p);
down_sum[p] += down_sum[e.first];
}
};
dfs1 (dfs1, stp, -1);
auto dfs2 = [&](auto& dfs2, int p, int par)->int {
for (pair <int, int>& e : gr[p])
if (e.first != par && !dis[e.first])
if (down_sum[e.first] > points.size() / 2)
return dfs2 (dfs2, e.first, p);
return p;
};
int centr = dfs2 (dfs2, stp, -1);
dis[centr] = 1;
can[0] = {0, step};
auto dfs3 = [&](auto& dfs3, int p, int par, int dep, int leng, bool save)->void {
if (leng > K)
return;
if (save) {
if (can[leng].second != step)
can[leng] = {dep, step};
else {
can[leng].first = min (can[leng].first, dep);
}
} else {
if (can[K - leng].second == step)
ans = min (ans, can[K - leng].first + dep);
}
for (pair <int, int>& e : gr[p])
if (e.first != par && !dis[e.first])
dfs3 (dfs3, e.first, p, dep + 1, leng + e.second, save);
};
for (pair <int, int>& e : gr[centr])
if (!dis[e.first]) {
dfs3 (dfs3, e.first, centr, 1, e.second, 0);
dfs3 (dfs3, e.first, centr, 1, e.second, 1);
}
for (pair <int, int>& e : gr[centr])
if (!dis[e.first])
f (f, e.first);
};
f (f, 0);
if (ans == 2e9)
return -1;
return ans;
}
