#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
vector<pair<int, int>> adj[N];
set<pair<ll, int>> s[N];
int ans = 1e9, K;
void dfs(int v, int p, ll val, int c) {
s[v].insert({ val,c });
for (auto& x : adj[v]) {
if (x.first == p) continue;
dfs(x.first, v, val + x.second, c + 1);
if (s[x.first].size() > s[v].size()) swap(s[x.first], s[v]);
for (auto& y : s[x.first]) {
auto it = s[v].lower_bound({ K + 2 * val - y.first,0 });
if (it == s[v].end()) continue;
if (it->first == K + 2 * val - y.first) ans = min(ans, it->second + y.second - 2 * c);
}
for (auto& y : s[x.first]) {
s[v].insert(y);
}
}
}
int best_path(int n, int k, int h[][2], int l[]) {
for (int i = 0;i < n - 1;i++) {
adj[h[i][0] + 1].push_back({ h[i][1] + 1, l[i] });
adj[h[i][1] + 1].push_back({ h[i][0] + 1, l[i] });
}
K = k;
dfs(1, 0, 0, 0);
if (ans == 1e9) return -1;
return ans;
}
