#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 <int> scr (N + 1);
vector <pair <int, int> > can (K + 1, {0, -1});
int ans = 2e9;
function <void(int)> f = [&](int stp) {
vector <int> points;
function <void(int,int)> dfs1 = [&](int p, int par) {
down_sum[p] = 1;
points.emplace_back (p);
for (pair <int, int>& e : gr[p])
if (e.first != par && !dis[e.first]) {
dfs1 (e.first, p);
down_sum[p] += down_sum[e.first];
}
};
dfs1 (stp, -1);
function <void(int,int)> dfs2 = [&](int p, int par) {
scr[p] = max (scr[p], (int)points.size() - down_sum[p]);
for (pair <int, int>& e : gr[p])
if (e.first != par && !dis[e.first]) {
dfs2 (e.first, p);
scr[p] = max (scr[p], down_sum[e.first]);
}
};
dfs2 (stp, -1);
int centr = stp;
for (auto e : points)
if (scr[e] < scr[centr])
centr = e;
dis[centr] = 1;
int cnt1 = 0;
function <void(int,int,int,int,bool)> dfs3 = [&](int p, int par, int dep, int leng, bool save) {
if (leng > K)
return;
if (save) {
if (can[leng].second != stp)
can[leng] = {dep, stp};
else {
can[leng].first = min (can[leng].first, dep);
}
} else {
if (can[K - leng].second == stp && can[K - leng].first > 0)
ans = min (ans, can[K - leng].first + dep);
if (leng == K)
ans = min (ans, dep);
}
for (pair <int, int>& e : gr[p])
if (e.first != par && !dis[e.first])
dfs3 (e.first, p, dep + 1, leng + e.second, save);
};
for (pair <int, int>& e : gr[centr])
if (!dis[e.first]) {
dfs3 (e.first, centr, 1, e.second, 0);
dfs3 (e.first, centr, 1, e.second, 1);
}
for (pair <int, int>& e : gr[centr])
if (!dis[e.first])
f (e.first);
};
f (0);
if (ans == 2e9)
return -1;
return ans;
}
