#include "race.h" #include <iostream> #include <vector> #include <utility> #include <map> using namespace std; using ll = long long; const int MAX_NODES_NUM = 2e5; const int INF = 1e9 + 7; int nodes_num, k; vector<pair<int, int>> tree[MAX_NODES_NUM+7]; bool used[MAX_NODES_NUM]; int sub_tree_size[MAX_NODES_NUM+7]; int res = INF; void genSubTreeSize(int node, int parent){ sub_tree_size[node] = 1; for (auto [next_node, _] : tree[node]) if (next_node != parent && !used[next_node]) { genSubTreeSize(next_node, node); sub_tree_size[node] += sub_tree_size[next_node]; } } int findCentroid(int node, int parent, int N){ for (auto [next_node, _] : tree[node]) if (next_node != parent && !used[next_node]) if (sub_tree_size[next_node] > N/2) return findCentroid(next_node, node, N); return node; } void genPaths(int node, int parent, ll whole_dist, int edges_num, vector<pair<ll, int>>& paths){ if (whole_dist > k) return; paths.push_back({whole_dist, edges_num}); for (auto [next_node, dist] : tree[node]) if (next_node != parent && !used[next_node]) genPaths(next_node, node, whole_dist + dist, edges_num+1, paths); } void processCentroid(int centroid) { map<ll, int> prev_paths; prev_paths[0] = 0; for (auto [next_node, dist] : tree[centroid]) if (!used[next_node]) { vector<pair<ll, int>> paths; genPaths(next_node, centroid, dist, 1, paths); for (auto [curr_dist, curr_edges_num] : paths){ int x_dist = k-curr_dist; if (prev_paths.count(x_dist)) res = min(res, prev_paths[x_dist] + curr_edges_num); } for (auto [curr_dist, curr_edges_num] : paths) if (prev_paths.count(curr_dist)) prev_paths[curr_dist] = min(prev_paths[curr_dist], curr_edges_num); else prev_paths[curr_dist] = curr_edges_num; } } void centroidDecomposition(int node) { genSubTreeSize(node, -1); int centroid = findCentroid(node, -1, sub_tree_size[node]); processCentroid(centroid); used[centroid] = true; for (auto[next_node, _] : tree[centroid]) if (!used[next_node]) centroidDecomposition(next_node); } int best_path(int N, int K, int H[][2], int L[]) { nodes_num = N; k = K; for (int i = 0; i < nodes_num-1; ++i){ int node_a = H[i][0], node_b = H[i][1], dist = L[i]; tree[node_a].push_back({node_b, dist}); tree[node_b].push_back({node_a, dist}); } centroidDecomposition(0); return (res == INF) ? -1 : res; }