#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
ll best_path(ll N, ll K, vector<pair<ll, ll>> H, vi L) {
ll ans = INT32_MAX;
vector<vector<pair<ll, ll>>> graph(N);
vi deg(N, 0);
for (ll i = 0; i < N-1; i++) {
auto& [a, b] = H[i];
graph[a].push_back({b, L[i]});
graph[b].push_back({a, L[i]});
deg[a] += 1;
deg[b] += 1;
}
queue<pair<ll, pair<ll, pair<ll, ll>>>> q;
q.push({0, {0, {0, 0}}}); // curr, parent, dist, depth
vector<bool> visited(N, false);
vi parent(N, -1), depth(N, -1), dist(N, -1);
while (!q.empty()) {
auto [curr, temp] = q.front(); q.pop();
auto [p, t] = temp;
auto [dis, dep] = t;
visited[curr] = true;
parent[curr] = p;
depth[curr] = dep;
dist[curr] = dis;
for (auto& [v, d] : graph[curr]) {
if (visited[v]) continue;
q.push({v, {curr, {dis+d, dep+1}}});
}
}
queue<ll> process;
vector<unordered_map<ll, ll>> sets(N);
for (ll i = 0; i < N; i++) {
if (deg[i] == 1) {
process.push(i);
}
sets[i][dist[i]] = depth[i];
}
while (!process.empty()) {
ll curr = process.front(); process.pop();
ll p = parent[curr];
if (sets[p].size() < sets[curr].size()) swap(sets[p], sets[curr]);
for (auto& [dis, dep] : sets[curr]) {
ll req = K + 2*dist[p] - dis;
if (sets[p].find(req) != sets[p].end()) {
ans = min(ans, dep + sets[p][req] - 2*depth[p]);
}
}
for (auto& [dis, dep] : sets[curr]) {
if (sets[p].find(dis) != sets[p].end()) {
sets[p][dis] = min(dep, sets[p][dis]);
} else sets[p][dis] = dep;
}
deg[p] -= 1;
if (deg[p] == 1) {
process.push(p);
}
}
return (ans == INT32_MAX) ? -1 : ans;
}
