#include "race.h"
#include "bits/stdc++.h"
using namespace std;
const int MXN = 200005;
const int MXD = 2000006;
int k;
int sz[MXN];
int dep[MXN];
long long dis[MXN];
vector<int> vec[MXN];
map<long long, multiset<int>> haveDis;
vector<pair<int, int>> g[MXN];
int ans;
int Dfs (int v, int p) {
sz[v] = 1;
for (auto [u, w] : g[v]) {
if (u != p) {
dis[u] = dis[v] + w;
dep[u] = dep[v] + 1;
sz[v] += Dfs(u, v);
}
}
return sz[v];
}
void Dfs2 (int v, int p, bool keep) {
int big = -1;
for (auto [u, w] : g[v]) {
if (u != p && (big == -1 || sz[u] > sz[big])) {
big = u;
}
}
for (auto [u, w] : g[v]) {
if (u != p && u != big) {
Dfs2(u, v, false);
}
}
if (big != -1) {
Dfs2(big, v, true);
swap(vec[v], vec[big]);
}
vec[v].push_back(v);
for (auto [u, w] : g[v]) {
if (u == p || u == big) {
continue;
}
for (int ch : vec[u]) {
long long needed = k - dis[ch] + 2 * dis[v];
if (needed >= 0 && !haveDis[needed].empty()) {
ans = min(ans, dep[ch] + *haveDis[needed].begin() - 2 * dep[v]);
}
}
for (int ch : vec[u]) {
vec[v].push_back(ch);
haveDis[dis[ch]].insert(dep[ch]);
}
}
long long needed = k + dis[v];
if (needed >= 0 && !haveDis[needed].empty()) {
ans = min(ans, *haveDis[needed].begin() - dep[v]);
}
if (!keep) {
for (int u : vec[v]) {
if (u != v) {
haveDis[dis[u]].erase(haveDis[dis[u]].find(dep[u]));
}
}
}
else {
haveDis[dis[v]].insert(dep[v]);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
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]);
}
ans = N + 1;
Dfs(0, 0);
Dfs2(0, 0, true);
return (ans == N + 1 ? -1 : ans);
}
