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