#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 200005
using ll = long long;
int n;
ll k;
ll di[MAX_N];
int dep[MAX_N];
vector<pair<int,int>> a[MAX_N];
set<pair<ll,int>> s[MAX_N];
const int INF = 1e9;
int dfs(int x, int p) {
int ans = INF;
s[x].insert({di[x], dep[x]});
int heavy = -1;
int mx = 0;
for (auto &e : a[x]) {
int y = e.first;
int w = e.second;
if (y == p) continue;
di[y] = di[x] + (ll)w;
dep[y] = dep[x] + 1;
ans = min(ans, dfs(y, x));
if (s[y].size() > mx) {
mx = s[y].size();
heavy = y;
}
}
if (heavy == -1) return ans;
swap(s[x], s[heavy]);
for (auto &e : a[x]) {
int y = e.first;
if (y == p) continue;
for (auto &pr : s[y]) {
ll dist_child = pr.first;
int depth_child = pr.second;
ll required = (k - (dist_child - di[x])) + di[x];
auto it = s[x].lower_bound({required, -1ll});
if (it != s[x].end() && (*it).first == required) {
int depth_here = (*it).second;
ans = min(ans, depth_child + depth_here - 2 * dep[x]);
}
}
for (auto &pr : s[y]) s[x].insert(pr);
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = (ll)K;
for (int i = 0; i < n - 1; ++i) {
int u = H[i][0], v = H[i][1], w = L[i];
a[u].push_back({v, w});
a[v].push_back({u, w});
}
di[0] = 0;
dep[0] = 0;
int ans = dfs(0, -1);
if (ans == INF) return -1;
return ans;
}
