#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 2e5 + 10;
int S[N], M[N], n, k, ret = 1e9; vector<pii> adj[N]; unordered_map<int, int> mp;
void preDFS(int v, int p = -1) {
S[v] = 1;
for (pii u : adj[v]) {
if (u.F != p && !M[u.F]) preDFS(u.F, v), S[v] += S[u.F];
}
}
int centroid(int v, int s, int p = -1) {
for (pii u : adj[v]) {
if (!M[u.F] && u.F != p && 2 * S[u.F] > s) return centroid(u.F, s, v);
}
return v;
}
void add(int v, int iw, int p, int h = 1) {
if (mp.count(iw)) mp[iw] = min(mp[iw], h);
else mp[iw] = h;
for (pii u : adj[v]) {
if (!M[u.F] && u.F != p) add(u.F, iw + u.S, v, h + 1);
}
}
void calc(int v, int iw, int p, int h = 1) {
if (iw > k) return;
if (iw == k) ret = min(ret, h);
else if (mp.count(k - iw)) ret = min(ret, h + mp[k - iw]);
for (pii u : adj[v]) {
if (!M[u.F] && u.F != p) calc(u.F, iw + u.S, v, h + 1);
}
}
void solve(int v) {
for (pii u : adj[v]) {
if (M[u.F]) continue;
calc(u.F, u.S, v);
add(u.F, u.S, v);
}
}
void decompose(int v) {
preDFS(v);
v = centroid(v, S[v]);
// solve
solve(v);
mp = {};
M[v] = 1;
for (pii u : adj[v]) if (!M[u.F]) decompose(u.F);
}
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] + 1, v = h[i][1] + 1;
adj[u].push_back({v, l[i]});
adj[v].push_back({u, l[i]});
}
decompose(1);
return ret == 1e9 ? -1 : ret;
}
