#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx = 2e5 + 5;
const int inf = 1e9;
int n, k;
vector<pair<int,ll>> adj[nx];
bool vis[nx];
int sz[nx];
int min_dist[1000005];
int ans = inf;
int getSize(int u, int pa) {
sz[u] = 1;
for (auto [v, w] : adj[u]) {
if (v == pa || vis[v]) continue;
sz[u] += getSize(v, u);
}
return sz[u];
}
int get_centroid(int u, int tree_size, int pa) {
for (auto [v, w] : adj[u]) {
if (v == pa || vis[v]) continue;
if (sz[v] * 2 > tree_size) return get_centroid(v, tree_size, u);
}
return u;
}
void get_dist(int u, int pa, ll w, int e, vector<pair<ll,int>> &dist) {
if (w > k) return;
dist.emplace_back(w, e);
for (auto [v, ww] : adj[u]) {
if (pa == v || vis[v]) continue;
get_dist(v, u, w + ww, e + 1, dist);
}
}
void solve(int u, int pa) {
int centroid = get_centroid(u, getSize(u, pa), pa);
vis[centroid] = 1;
u = centroid;
vector<int> touched;
if (min_dist[k] != inf) {
ans = min(ans, min_dist[k]);
}
min_dist[0] = 0;
for (auto [v, ww] : adj[u]) {
if (vis[v] || v == pa) continue;
vector<pair<ll,int>> dist;
get_dist(v, u, ww, 1, dist);
for (auto [w, e] : dist) {
if (w <= k && min_dist[k - w] != inf) ans = min(ans, e + min_dist[k - w]);
}
for (auto [w, e] : dist) {
if (e >= min_dist[w]) continue;
min_dist[w] = min(min_dist[w], e);
touched.emplace_back(w);
}
}
for (auto idx : touched) min_dist[idx] = inf;
for (auto [v, ww] : adj[centroid]) {
if (v == pa || vis[v]) continue;
solve(v, centroid);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for (int i = 0; i < n - 1; i++) {
int u = H[i][0], v = H[i][1], w = L[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
for (int i = 1; i <= k; i++) min_dist[i] = inf;
solve(0, -1);
if (ans == inf) return -1;
return ans;
}
