#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int max_N = 200003, max_K = 1000003, INF = 1e9;
int n, k, sz[max_N], mx[max_N], del[max_N], val[max_K], ans;
vector <pii> adj[max_N];
void dfs(int v, int p) {
sz[v] = 1;
mx[v] = -1;
for (auto i : adj[v]) {
int to = i.F;
if (to == p || del[to]) {
continue;
}
dfs(to, v);
sz[v] += sz[to];
if (mx[v] == -1 || sz[mx[v]] < sz[to]) {
mx[v] = to;
}
}
}
int centroid(int v) {
int u = v;
while (mx[v] != -1 && sz[mx[v]] > sz[u] / 2) {
v = mx[v];
}
return v;
}
void add(int v, int p, int d, int l) {
if (d > k) {
return;
}
val[d] = min(val[d], l);
for (auto i : adj[v]) {
int to = i.F, w = i.S;
if (to == p || del[to]) {
continue;
}
add(to, v, d + w, l + 1);
}
}
void calc(int v, int p, int d, int l) {
if (d > k) {
return;
}
ans = min(ans, val[k - d] + l);
for (auto i : adj[v]) {
int to = i.F, w = i.S;
if (to == p || del[to]) {
continue;
}
calc(to, v, d + w, l + 1);
}
}
void clear(int v, int p, int d, int l) {
if (d > k) {
return;
}
val[d] = INF;
for (auto i : adj[v]) {
int to = i.F, w = i.S;
if (to == p || del[to]) {
continue;
}
clear(to, v, d + w, l + 1);
}
}
void solve(int v) {
val[0] = 0;
for (auto i : adj[v]) {
int to = i.F, w = i.S;
if (del[to]) {
continue;
}
calc(to, v, w, 1);
add(to, v, w, 1);
}
for (auto i : adj[v]) {
int to = i.F, w = i.S;
if (del[to]) {
continue;
}
clear(to, v, w, 1);
}
}
void build(int v, int d) {
dfs(v, -1);
int c = centroid(v);
solve(c);
del[c] = 1;
for (auto i : adj[c]) {
int to = i.F;
if (!del[to]) {
build(to, d + 1);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
memset(& del, 0, sizeof(del));
for (int i = 0; i < n - 1; i++) {
adj[i].clear();
}
ans = max_N;
for (int i = 0; i < n - 1; i++) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
memset(& val, 0x3f, sizeof(val));
build(0, 0);
if (ans == max_N) {
return -1;
}
return ans;
}
