#include "race.h" #include <iostream> #include <vector> #include <unordered_map> #include <random> 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){ int mxSz=0, mxJ=-1, mxJW; for (auto [j, w] : G[i]){ if (j != p && subTreeSz[j] > mxSz){ mxSz = subTreeSz[j]; mxJ = j; mxJW = w; } } if (mxJ == -1){ minRoads[0] = 0; addLength = addRoads = 0; return; } dfs(mxJ, i, addLength, addRoads, res, minRoads, G, subTreeSz, K); addLength += mxJW; ++addRoads; //minRoads[-addLength] = -addRoads; 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 (auto [l, cnt] : auxMinRoads){ int nl = K-(l+w+auxAddL), ncnt = 1+cnt+auxAddR; if (minRoads.count(nl-addLength)){ res = min(res, minRoads[nl-addLength]+addRoads+ncnt); } } for (auto [l, cnt] : auxMinRoads){ int nl = l+w+auxAddL-addLength; int ncnt = cnt+1+auxAddR-addRoads; if (!minRoads.count(nl)){ minRoads[nl] = ncnt; } else { minRoads[nl] = min(minRoads[nl], ncnt); } } } if (minRoads.count(K - addLength)){ res = min(res, minRoads[K - addLength]+addRoads); } } 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); res = (res==INF ? -1 : res); return (signed)res; } /* signed main(){ signed N, K; cin >> N >> K; signed H[N-1][2]; signed L[N-1]; 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; } /* 4 5 0 1 3 1 2 1 1 3 4 -1 */