#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);
int ans = 2e9;
function <void(int)> f = [&](int stp) {
map <int, int> down_sum;
map <int, int> scr;
function <void(int,int)> dfs1 = [&](int p, int par) {
down_sum[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)down_sum.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 [a, b] : scr)
if (b < scr[centr])
centr = a;
dis[centr] = 1;
map <int, int> can;
int cnt1 = 0;
function <void(int,int,int,int,bool)> dfs3 = [&](int p, int par, int dep, int leng, bool save) {
if (save) {
if (can[leng] == 0)
can[leng] = dep;
else
can[leng] = min (can[leng], dep);
} else {
if (can[K - leng] > 0)
ans = min (ans, can[K - leng] + 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;
}
