#include "race.h" #include <iostream> #include <vector> #include <unordered_map> using namespace std; #define int long long #define pi pair<int,int> const int INF = 3e18; // map -> length <-> min nºroads (ending on our vertex i) // int 1 -> we sum this num to all lengths (to let us use S2L) // int 2 -> the same but to nºroads int dfs_sz(int i, int p, vector<vector<pi> > & G, vector<int> & subTreeSz){ int res=1; for (auto[j,w] : G[i]){ if (j == p) continue; res += dfs_sz(j, i, G, subTreeSz); } return subTreeSz[i] = res; } void dfs(int i, int p, int & addLength, int & addRoads, int & res, unordered_map<int,int> & minRoads, vector<vector<pi> > & G, vector<int> & subTreeSz, int K){ // find heavy child int mxSz=0, mxJ=-1, mxJW=0; for (auto [j, w] : G[i]){ if (j != p && subTreeSz[j] > mxSz){ mxSz = subTreeSz[j]; mxJ = j; mxJW = w; } } if (mxJ == -1){ // leaf: only zero-length path (ending at this vertex) with 0 roads minRoads.clear(); minRoads[0] = 0; addLength = 0; addRoads = 0; return; } // process heavy child first (we'll keep its minRoads and offsets in-place) dfs(mxJ, i, addLength, addRoads, res, minRoads, G, subTreeSz, K); // move offsets up across edge (i <-> mxJ) addLength += mxJW; ++addRoads; // For every other child, process and merge into minRoads (which currently holds heavy child's data) for (auto [j, w] : G[i]){ if (j == p || j == mxJ) continue; unordered_map<int, int> auxMinRoads; int auxAddL = 0, auxAddR = 0; dfs(j, i, auxAddL, auxAddR, res, auxMinRoads, G, subTreeSz, K); // For each real entry in auxMinRoads, convert to current coordinate and try to pair for (auto &entry : auxMinRoads){ int stored_l_in_aux = entry.first; // stored key in aux: real_len_aux - auxAddL int stored_cnt_in_aux = entry.second; // stored val in aux: real_edges_aux - auxAddR // get real values for a node in aux subtree (including edge w from i to that subtree) int real_len_aux = stored_l_in_aux + auxAddL + w; // l + auxAddL + w int real_edges_aux = stored_cnt_in_aux + auxAddR + 1; // cnt + auxAddR + 1 if (real_len_aux > K) continue; // cannot contribute to K // in minRoads the stored key is: stored_key = real_len_other - addLength // we need real_len_other = K - real_len_aux int needed_real_other = (int)K - real_len_aux; int needed_stored_key = needed_real_other - addLength; auto it = minRoads.find(needed_stored_key); if (it != minRoads.end()){ // it->second is stored value: stored_edges_other = real_edges_other - addRoads int real_edges_other = it->second + addRoads; int total_edges = real_edges_aux + real_edges_other; if (total_edges < res) res = total_edges; } } // After checking combinations, merge aux entries into minRoads (store them in current stored coordinate) for (auto &entry : auxMinRoads){ int stored_l_in_aux = entry.first; int stored_cnt_in_aux = entry.second; int real_len_aux = stored_l_in_aux + auxAddL + w; // actual length int real_edges_aux = stored_cnt_in_aux + auxAddR + 1; // actual edges if (real_len_aux > K) continue; // no need to store lengths > K int stored_key_in_current = real_len_aux - addLength; // stored key relative to current addLength int stored_val_in_current = real_edges_aux - addRoads; // stored val relative to current addRoads auto it = minRoads.find(stored_key_in_current); if (it == minRoads.end()){ minRoads[stored_key_in_current] = stored_val_in_current; } else { if (stored_val_in_current < it->second) it->second = stored_val_in_current; } } } // Finally, check if any path entirely within the heavy side (i.e., using minRoads) gives length K int needed_stored = (int)K - addLength; // stored key corresponding to real length K auto itf = minRoads.find(needed_stored); if (itf != minRoads.end()){ int real_edges = itf->second + addRoads; if (real_edges < res) res = real_edges; } } signed best_path(signed N, signed K, signed H[][2], signed L[]){ vector<vector<pi> > G(N); for (int i=0; i<N-1; ++i){ int u = H[i][0], v = H[i][1]; int w = L[i]; G[u].push_back(pi(v,w)); G[v].push_back(pi(u,w)); } vector<int> subTreeSz(N); dfs_sz(0, -1, G, subTreeSz); unordered_map<int, int> minRoads; int addLength=0, addRoads=0; int res=INF; dfs(0, -1, addLength, addRoads, res, minRoads, G, subTreeSz, K); signed nres = (res>=INF ? -1 : res); return nres; } /* signed main(){ int N, K; cin >> N >> K; vector<vector<int> > H(N, vector<int>(2)); vector<int> L(N); for (int i=0; i<N-1; ++i){ cin >> H[i][0] >> H[i][1] >> L[i]; } cout << best_path(N, K, H, L) << '\n'; return 0; } */