#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 5;
const int oo = 1e9;
int n, k;
vector<array<int, 2>> adj[NN];
struct CentroidDecomposition {
vector<int> sub;
vector<bool> removed;
vector<int> mn;
vector<int> touched;
void init(int n) {
sub.assign(n + 1, 0);
removed.assign(n + 1, false);
mn.assign(k + 1, oo);
}
int getsub(int u, int p) {
sub[u] = 1;
for (auto &[v, w] : adj[u]) {
if (v != p && !removed[v]) sub[u] += getsub(v, u);
}
return sub[u];
}
int find_centroid(int u, int p, int half) {
for (auto &[v, w] : adj[u]) {
if (v != p && !removed[v] && sub[v] > half) return find_centroid(v, u, half);
}
return u;
}
void getdist(int u, int p, int d, int we, vector<array<int, 2>> &dist) {
if (we > k) return;
dist.push_back({we, d});
for (auto &[v, w] : adj[u]) {
if (v != p && !removed[v]) getdist(v, u, d + 1, we + w, dist);
}
}
int solveK(int centroid) {
int res = oo;
touched.clear();
mn[0] = 0;
touched.push_back(0);
for (auto &[v, w0] : adj[centroid]) {
if (removed[v]) continue;
vector<array<int, 2>> dist;
getdist(v, centroid, 1, w0, dist);
for (auto &[we, d] : dist) {
if (we <= k && mn[k - we] != oo) {
res = min(res, mn[k - we] + d);
}
}
for (auto &[we, d] : dist) {
if (we <= k && d < mn[we]) {
if (mn[we] == oo) touched.push_back(we);
mn[we] = d;
}
}
}
for (int x : touched) mn[x] = oo;
return res;
}
int solve(int u) {
int sz = getsub(u, -1);
int centroid = find_centroid(u, -1, sz >> 1);
int res = solveK(centroid);
removed[centroid] = true;
for (auto &[v, w] : adj[centroid]) {
if (!removed[v]) res = min(res, solve(v));
}
removed[centroid] = false;
return res;
}
};
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 1; i <= n; ++i) adj[i].clear();
for (int i = 0; i < n - 1; ++i) {
int u = H[i][0] + 1;
int v = H[i][1] + 1;
adj[u].push_back({v, L[i]});
adj[v].push_back({u, L[i]});
}
CentroidDecomposition cd;
cd.init(n + 5);
int res = cd.solve(1);
return (res == oo ? -1 : res);
}
