#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int K;
vector<vector<pair<int, int>>> adjlist;
vector<long long> dists;
vector<int> d;
vector<set<pair<long long, int>>> sets;
void dfs(int n, int p) {
for (auto i : adjlist[n]) {
if (i.first == p) continue;
dists[i.first] = dists[n] + i.second;
d[i.first] = d[n] + 1;
dfs(i.first, n);
}
}
int dfs1(int n, int p) {
int res = INT_MAX;
for (auto i : adjlist[n]) {
if (i.first == p) continue;
res = min(res, dfs1(i.first, n));
}
for (auto i : adjlist[n]) {
if (i.first == p) continue;
if (sets[n].size() < sets[i.first].size()) swap(sets[n], sets[i.first]);
for (auto j : sets[i.first]) {
auto iter = sets[n].lower_bound({K - j.first + 2 * dists[n], 0});
if (iter != sets[n].end() && iter->first == K - j.first + 2 * dists[n]) res = min(res, j.second + iter->second - 2 * d[n]);
}
for (auto j : sets[i.first]) sets[n].insert(j);
}
return res;
}
int best_path(int N, int _K, int H[][2], int L[]) {
K = _K;
adjlist.resize(N, vector<pair<int, int>>());
dists.resize(N, 0);
sets.resize(N, set<pair<long long, int>>());
d.resize(N, 0);
for (int i = 0; i < N - 1; i++) {
adjlist[H[i][0]].push_back({ H[i][1], L[i] });
adjlist[H[i][1]].push_back({ H[i][0], L[i] });
}
dfs(0, -1);
for (int i = 0; i < N; i++) sets[i].insert({ dists[i], d[i] });
int res = dfs1(0, -1);
return (res == INT_MAX ? -1 : res);
}
