#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5 + 5;
vector<pair<int, int>> adj[mxn];
int del[mxn], sz[mxn];
map<int, int> mp;
vector<pair<int, int>> tmp;
int res = 2e9;
void dfs(int x, int par = -1) {
sz[x] = 1;
for (auto [w, p] : adj[x]) {
if (p == par || del[p]) continue;
dfs(p, x);
sz[x] += sz[p];
}
}
int centroid(int x, int n, int par = -1) {
for (auto [w, p] : adj[x]) {
if (p == par || del[p]) continue;
if (sz[p] * 2 > n) return centroid(p, n, x);
}
return x;
}
void dfs2(int k, int x, int par, int dis, int cnt) {
if (dis > k) return;
tmp.push_back({dis, cnt});
if (mp.find(k - dis) != mp.end()) res = min(res, mp[k - dis] + cnt);
for (auto [w, p] : adj[x]) {
if (p == par || del[p]) continue;
dfs2(k, p, x, dis + w, cnt + 1);
}
}
void solve(int k, int x) {
dfs(x);
int c = centroid(x, sz[x]);
mp.clear(), tmp.clear();
mp[0] = 0;
for (auto [w, i] : adj[c]) {
if (!del[i]) {
dfs2(k, i, c, w, 1);
for (auto [d, c] : tmp) {
if (mp.find(d) == mp.end()) mp[d] = c;
else mp[d] = min(mp[d], c);
}
tmp.clear();
}
}
del[c] = 1;
for (auto [w, i] : adj[c]) {
if (!del[i]) solve(k, i);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].push_back({L[i], H[i][1]});
adj[H[i][1]].push_back({L[i], H[i][0]});
}
solve(K, 0);
if (res == 2e9) return -1;
return res;
}
