#include "race.h" #include <vector> #include <unordered_map> using namespace std; const int NMAX = 2e5; const int KMAX = 1e6; const int INF = 1e9; int n, k; vector<pair<int, int>> g[NMAX + 1]; int sub[NMAX + 1]; bool done[NMAX + 1]; unordered_map<int, int> pref_min; void get_sizes(int node, int dad = 0) { sub[node] = 1; for(auto [next_node, c] : g[node]) { if(next_node != dad && !done[next_node]) { get_sizes(next_node, node); sub[node] += sub[next_node]; } } } int get_centroid(int node, int root_sz, int dad = 0) { for(auto [next_node, c] : g[node]) { if(next_node != dad && !done[next_node] && sub[next_node] > root_sz / 2) { return get_centroid(next_node, root_sz, node); } } return node; } int get_answer(int node, int dad, int curent_c, int depth = 1) { if(curent_c > k) { return INF; } int answer = (pref_min.count(k - curent_c) ? pref_min[k - curent_c] + depth : INF); for(auto [next_node, c] : g[node]) { if(next_node != dad && !done[next_node]) { answer = min(answer, get_answer(next_node, node, curent_c + c, depth + 1)); } } return answer; } void add_sub(int node, int dad, int curent_c, int depth = 1) { if(curent_c > k) { return; } pref_min[curent_c] = (pref_min.count(curent_c) ? min(pref_min[curent_c], depth) : depth); for(auto [next_node, c] : g[node]) { if(next_node != dad && !done[next_node]) { add_sub(next_node, node, curent_c + c, depth + 1); } } } int solve(int node) { get_sizes(node); int centroid = get_centroid(node, sub[node]); int answer = INF; pref_min[0] = 0; for(auto [next_node, c] : g[centroid]) { if(!done[next_node]) { answer = min(answer, get_answer(next_node, centroid, c)); add_sub(next_node, centroid, c); } } done[centroid] = 1; for(auto [next_node, c] : g[centroid]) { if(!done[next_node]) { answer = min(answer, solve(next_node)); } } return answer; } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; for(int i = 1; i <= n - 1; i++) { int a = H[i - 1][0], b = H[i - 1][1], c = L[i - 1]; a++; b++; g[a].push_back({b, c}); g[b].push_back({a, c}); } int answer = solve(1); return (answer == INF ? -1 : answer); }