#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, ans = 1e9, k;
vector<vector<pair<int, int>>> g;
map<ll, int> mp[(int)2e5 + 5];
// small to large
void dfs(int u = 0, int p = -1, int w = 0, int d = 0) {
mp[u][w] = d;
for (auto [v, c] : g[u]) {
if (v ^ p) {
dfs(v, u, w + c, d + 1);
if (mp[v].size() > mp[u].size())
swap(mp[u], mp[v]);
for (auto [cost, dep] : mp[v]) {
ll rem = 1 * k + 2 * w - cost;
auto it = mp[u].find(rem);
if (it != mp[u].end())
ans = min(ans, it->second + dep - 2 * d);
}
for (auto [cost, dep] : mp[v]) {
auto it = mp[u].find(cost);
if (it == mp[u].end())
mp[u][cost] = dep;
else
it->second = min(it->second, dep);
}
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
g.resize(n = N);
k = K;
for (int i = 0; i < n - 1; ++i) {
g[H[i][0]].emplace_back(H[i][1], L[i]);
g[H[i][1]].emplace_back(H[i][0], L[i]);
}
dfs();
return ans == 1e9 ? -1 : ans;
}
// int main() {
// int H[3][2] = {{0, 1}, {1, 2}, {1, 3}};
// int L[3] = {1, 2, 4};
// cout << best_path(4, 3, H, L);
// }
