#include "race.h"
#include <bits/stdc++.h>
using namespace std;
void recurse(int N, int K, vector<vector<pair<int, int>>> &adjacency, vector<map<int, int>> &maps, int &res, int cur, int parent) {
maps[cur][0] = 0;
for (auto &[child, length] : adjacency[cur]) {
if (child == parent) continue;
recurse(N, K, adjacency, maps, res, child, cur);
for (auto i = prev(maps[child].end()); ; ) {
auto &[a, b] = *i;
bool bre = true;
if (i != maps[child].begin()) bre = false, --i;
maps[child].erase(a);
if (a + length <= K) maps[child][a + length] = b + 1;
if (bre) break;
}
if (maps[cur].size() < maps[child].size()) swap(maps[cur], maps[child]);
maps[cur][0] = maps[child][0] = 0;
for (auto &[i, j] : maps[child]) {
if (maps[cur].count(K - i)) res = min(res, j + maps[cur][K - i]);
}
for (auto &[i, j] : maps[child]) {
if (maps[cur].count(i)) maps[cur][i] = min(maps[cur][i], j);
else maps[cur][i] = j;
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pair<int, int>>> adjacency(N);
for (int i = 0; i < N - 1; ++i) {
adjacency[H[i][0]].emplace_back(H[i][1], L[i]);
adjacency[H[i][1]].emplace_back(H[i][0], L[i]);
}
vector<map<int, int>> maps(N);
int res = 1e9;
recurse(N, K, adjacency, maps, res, 0, -1);
return (res < 1e9 ? res : -1);
}
