#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 1e6+10;
const int oo = 1e9;
int n, k, ans, table[M];
vector<vector<pair<int,int>>> g;
int sub[N];
bool bad[N];
void dfs_siz (int u, int f) {
sub[u] = 1;
for (auto [v, w] : g[u]) if (!bad[v] && v ^ f) dfs_siz(v, u), sub[u] += sub[v];
}
int fc (int u, int f, int lim) {
for (auto [v, w] : g[u]) if (!bad[v] && v ^ f && sub[v] > lim) return fc(v, u, lim);
return u;
}
void dfs (int u, int f, int dist, int edgecnt, int ty) {
if (dist > k) return;
if (ty == 0) ans = min(ans, table[k - dist] + edgecnt);
else if (ty == 1) table[dist] = min(table[dist], edgecnt);
else table[dist] = oo;
for (auto [v, w] : g[u]) if (!bad[v] && v ^ f)
dfs(v, u, dist + w, edgecnt + 1, ty);
}
void decompose (int u) {
dfs_siz(u, 0); u = fc(u, 0, sub[u] >> 1);
bad[u] = true;
table[0] = 0;
for (auto [v, w] : g[u]) if (!bad[v]) {
dfs(v, u, w, 1, 0);
dfs(v, u, w, 1, 1);
}
table[0] = oo;
for (auto [v, w] : g[u]) if (!bad[v]) dfs(v, u, w, 1, -1);
for (auto [v, w] : g[u]) if (!bad[v]) decompose(v);
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
g.resize(n);
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]});
}
fill(table, table + k + 1, oo); ans = oo;
decompose(1);
if (ans == oo) ans = -1;
return ans;
}
