#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
const int L = 2000000;
const int INF = 1e9;
struct edge {
int to;
int w;
};
int n, k;
int sz[N];
bool rmv[N];
vector<edge> g[N];
int calc(int s, int p) {
sz[s] = 1;
for (auto [to, w] : g[s]) {
if (to == p || rmv[to]) continue;
sz[s] += calc(to, s);
}
return sz[s];
}
int find_centroid(int s, int p, int m) {
for (auto [to, w] : g[s]) {
if (to == p || rmv[to]) continue;
if (sz[to] * 2 > m)
return find_centroid(to, s, m);
}
return s;
}
int answer;
int mp[L];
void get_answer(int s, int p, int dep, int len) {
if (len <= k)
answer = min(answer, mp[k - len] + dep);
for (auto [to, w] : g[s]) {
if (to == p || rmv[to]) continue;
get_answer(to, s, dep + 1, len + w);
}
}
void add_to_map(int s, int p, int dep, int len) {
if (len <= k)
mp[len] = min(mp[len], dep);
for (auto [to, w] : g[s]) {
if (to == p || rmv[to]) continue;
add_to_map(to, s, dep + 1, len + w);
}
}
void clear_map(int s, int p, int dep, int len) {
if (len <= k)
mp[len] = INF;
for (auto [to, w] : g[s]) {
if (to == p || rmv[to]) continue;
clear_map(to, s, dep + 1, len + w);
}
}
void decompose(int s) {
int C = find_centroid(s, s, calc(s, s));
mp[0] = 0;
for (auto [to, w] : g[C]) {
if (rmv[to]) continue;
get_answer(to, C, 1, w);
add_to_map(to, C, 1, w);
}
for (auto [to, w] : g[C]) {
if (rmv[to]) continue;
clear_map(to, C, 1, w);
}
mp[0] = INF;
rmv[C] = true;
for (auto [to, w] : g[C]) {
if (!rmv[to])
decompose(to);
}
}
int best_path(int n_inside, int k_inside, int H[][2], int L[]) {
n = n_inside;
k = k_inside;
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]});
}
answer = INF;
for (int x = 0; x <= k; x++)
mp[x] = INF;
decompose(1);
if (answer == INF)
return -1;
return answer;
}
