#include "race.h"
#include <vector>
#include <climits>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<vector<pair<int,int>>> g; // {сосед, длина дороги}
int N, K;
void dfs_paths(int v, int p, int len, int edges, vector<pair<int,int>> &paths) {
if(len > K) return; // отсечка
paths.push_back({len, edges});
for(auto &k : g[v]) {
if(k.first != p) {
dfs_paths(k.first, v, len + k.second, edges + 1, paths);
}
}
}
int best_path(int n, int k, int H[][2], int L[]) {
N = n;
K = k;
g.clear();
g.resize(N);
// строим дерево
for(int i=0; i<N-1; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
int answer = INT_MAX;
// для каждой вершины
for(int v=0; v<N; v++) {
vector<vector<pair<int,int>>> children_paths;
// получаем все пути из соседних поддеревьев
for(auto &k : g[v]) {
vector<pair<int,int>> paths;
dfs_paths(k.first, v, k.second, 1, paths);
children_paths.push_back(paths);
}
// объединяем пути через вершину v
unordered_map<int,int> mp; // длина -> минимальное количество рёбер
for(auto &paths : children_paths) {
for(auto &[len, edges] : paths) {
if(mp.count(K - len)) {
answer = min(answer, edges + mp[K - len]);
}
}
for(auto &[len, edges] : paths) {
if(!mp.count(len) || edges < mp[len]) mp[len] = edges;
}
}
// проверка одиночных поддеревьев (если путь начинается и заканчивается в одном поддереве)
for(auto &paths : children_paths) {
for(auto &[len, edges] : paths) {
if(len == K) answer = min(answer, edges);
}
}
}
if(answer == INT_MAX) return -1;
return answer;
}
