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