#include <bits/stdc++.h>
using namespace std;
#include "race.h"
vector<set<pair<int64_t, int64_t>>> s;
vector<pair<int64_t, int64_t>> c;
vector<vector<pair<int64_t, int64_t>>> g;
int64_t min_edges_num = INT_MAX;
void find_best(int64_t u, int64_t p, int64_t k)
{
if (g[u].size() == 1 && g[u].front().first == p)
{
s[u].emplace(0, 0);
c[u] = {0, 0};
return;
}
int64_t max_v, max_size = 0, max_w;
for (auto const &[v, w] : g[u])
if (v != p)
{
find_best(v, u, k);
if (s[v].size() >= max_size)
max_v = v, max_size = s[v].size(), max_w = w;
}
swap(s[u], s[max_v]);
swap(c[u], c[max_v]);
c[u].first += max_w;
c[u].second++;
for (auto const &[v, w] : g[u])
if (v != p && v != max_v)
{
for (auto const &[length, num_edges] : s[v])
{
auto it = s[u].lower_bound({k - (length + w + c[v].first) - c[u].first, INT_MIN});
if (it != s[u].end() && it->first + c[u].first + length + w + c[v].first == k)
min_edges_num = min(min_edges_num, it->second + c[u].second + num_edges + 1 + c[v].second);
}
for (auto const &[length, num_edges] : s[v])
{
s[u].emplace(length + w + c[v].first - c[u].first,
num_edges + 1 + c[v].second - c[u].second);
}
}
auto it = s[u].lower_bound({k - c[u].first, INT_MIN});
if (it != s[u].end() && it->first + c[u].first == k)
min_edges_num = min(min_edges_num, it->second + c[u].second);
s[u].emplace(-c[u].first, -c[u].second);
}
int best_path(int N, int K, int H[][2], int L[])
{
g = vector<vector<pair<int64_t, int64_t>>>(N);
s = vector<set<pair<int64_t, int64_t>>>(N);
c = vector<pair<int64_t, int64_t>>(N);
for (int64_t 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]);
}
find_best(0, -1, K);
return min_edges_num == INT_MAX ? -1 : min_edges_num;
}
