#include "race.h"
#include <vector>
#include <unordered_map>
using namespace std;
const int NMAX = 2e5;
const int KMAX = 1e6;
const int INF = 1e9;
int n, k;
vector<pair<int, int>> g[NMAX + 1];
int sub[NMAX + 1];
bool done[NMAX + 1];
int pref_min[KMAX + 1];
void get_sizes(int node, int dad = 0) {
sub[node] = 1;
for(auto [next_node, c] : g[node]) {
if(next_node != dad && !done[next_node]) {
get_sizes(next_node, node);
sub[node] += sub[next_node];
}
}
}
int get_centroid(int node, int root_sz, int dad = 0) {
for(auto [next_node, c] : g[node]) {
if(next_node != dad && !done[next_node] && sub[next_node] > root_sz / 2) {
return get_centroid(next_node, root_sz, node);
}
}
return node;
}
int get_answer(int node, int dad, int curent_c, int depth = 1) {
if(curent_c > k) {
return INF;
}
int answer = pref_min[k - curent_c] + depth;
for(auto [next_node, c] : g[node]) {
if(next_node != dad && !done[next_node]) {
answer = min(answer, get_answer(next_node, node, curent_c + c, depth + 1));
}
}
return answer;
}
void add_sub(int node, int dad, int curent_c, int depth = 1) {
if(curent_c > k) {
return;
}
pref_min[curent_c] = min(pref_min[curent_c], depth);
for(auto [next_node, c] : g[node]) {
if(next_node != dad && !done[next_node]) {
add_sub(next_node, node, curent_c + c, depth + 1);
}
}
}
void delete_sub(int node, int dad, int curent_c) {
if(curent_c > k) {
return;
}
pref_min[curent_c] = INF;
for(auto [next_node, c] : g[node]) {
if(next_node != dad && !done[next_node]) {
delete_sub(next_node, node, curent_c + c);
}
}
}
int solve(int node) {
get_sizes(node);
int centroid = get_centroid(node, sub[node]);
int answer = INF;
pref_min[0] = 0;
for(auto [next_node, c] : g[centroid]) {
if(!done[next_node]) {
answer = min(answer, get_answer(next_node, centroid, c));
add_sub(next_node, centroid, c);
}
}
for(auto [next_node, c] : g[centroid]) {
if(!done[next_node]) {
delete_sub(next_node, centroid, c);
}
}
done[centroid] = 1;
for(auto [next_node, c] : g[centroid]) {
if(!done[next_node]) {
answer = min(answer, solve(next_node));
}
}
return answer;
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for(int i = 1; i <= n - 1; i++) {
int a = H[i - 1][0], b = H[i - 1][1], c = L[i - 1];
a++; b++;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
fill(pref_min, pref_min + k + 1, INF);
int answer = solve(1);
return (answer == INF ? -1 : answer);
}
