#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = (int)(2e5 + 5);
ll K;
vector<pair<int, int>> adj[MAXN];
struct paths {
ll addL = 0;
int addV = 0;
unordered_map<ll, int> mn;
paths() {
mn[0] = 0;
}
bool contains(ll a) {
return mn.count(a-addL);
}
int get(ll a) {
if (!contains(a)) {
return 2*MAXN;
}
return mn[a-addL] + addV;
}
void insert(ll v, int cnt) {
if(get(v) > cnt) {
mn[v-addL] = cnt-addV;
}
}
int size() {
return mn.size();
}
};
paths keep[MAXN];
int res = MAXN;
void dfs(int n, int p) {
for (auto& e : adj[n]) {
if (e.first != p) {
dfs(e.first, n);
keep[e.first].addL += e.second;
keep[e.first].addV++;
if (keep[n].size() < keep[e.first].size()) {
swap(keep[e.first], keep[n]);
}
for (auto& keypair : keep[e.first].mn) {
ll od = keypair.first + keep[e.first].addL;
if (keep[n].contains(K-od)) {
res = min(keypair.second + keep[e.first].addV + keep[n].get(K-od), res);
}
}
for (auto& keypair : keep[e.first].mn) {
keep[n].insert(keypair.first + keep[e.first].addL, keypair.second + keep[e.first].addV);
}
}
}
}
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({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
K = k;
dfs(0, 0);
return (res == MAXN ? -1 : res);
}
