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