#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
#define NN 200010
#define F(i, l, r) for (ll i = (l); i < (r); ++i)
vector<pl> adj[NN];
struct mp {
ll plen = 0, pwe = 0;
map<ll, ll> mp; // maps weight -> lens, lazy updates and shit
void insert(ll k, ll w) {
k -= pwe; w -= plen;
if (!mp.count(k)) mp[k] = w;
else mp[k] = min(w, mp[k]);
}
ll query(ll k) {
k -= pwe;
if (!mp.count(k)) return 1e9;
return mp[k] + plen;
}
vector<pl> getall() const {
vector<pl> res;
for (const auto &[k, v]: mp) res.emplace_back(k + pwe, v + plen);
return res;
}
};
ll ans, k;
mp dfs(ll i, ll p) {
mp cur;
for (auto [x, w]: adj[i]) if (x-p) {
auto child = dfs(x, i);
child.plen++; child.pwe+=w;
ans = min(ans, child.query(k));
if (cur.mp.size() < child.mp.size()) swap(cur, child);
for (const auto [cpath, clen]: child.getall()) {
ans = min(ans, cur.query(k - cpath) + clen);
cur.insert(cpath, clen);
}
}
cur.insert(0, 0);
return cur;
}
int best_path(int N, int K, int H[][2], int L[])
{
F(i, 0, N-1) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
ans = N;
k = K;
dfs(0, 0);
return ans == N ? -1: ans;
}
