#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; }