#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>
#define MAX 200000
#define des first
#define d second
vector<pll> hijos[MAX+2];
lli n,k,res,act,padre,mitad;
//centroid
lli tam[MAX+2],vis[MAX+2];
queue<lli> cola;
bool cond;
map<lli,lli> abso,rama;
void dfs(lli pos, lli p) {
tam[pos] = 1;
for(auto h : hijos[pos]) {
if (vis[h.des] == 1 || h.des == p) continue;
dfs(h.des,pos);
tam[pos] += tam[h.des];
}
}
void sub(lli pos, lli p,lli cam, lli sum) {
//checa contra abso
if (sum > k) return;
lli x,a = k-sum;
if (abso.find(a) != abso.end()) {
x = abso[a] + cam;
if (res == -1 || res > x) res = x;
}
//me meto a rama
if (rama.find(sum) != rama.end()) rama[sum] = min(rama[sum],cam);
else rama[sum] = cam;
//sigo procesando el subarbol
for(auto h : hijos[pos]) {
if (h.des == p || vis[h.des] == 1) continue;
sub(h.des,pos,cam+1,sum+h.d);
}
}
void solve(lli raiz) {
abso.clear();
abso[0] = 0;
for(auto h : hijos[raiz]) {
if (vis[h.des] == 1) continue;
rama.clear();
sub(h.des,raiz,1,h.d);
if (rama.size() > abso.size()) swap(abso,rama);
for (auto act : rama) {
if (abso.find(act.first) != abso.end()) abso[act.first] = min(abso[act.first], act.second);
else abso[act.first] = act.second;
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
res = -1;
rep(i,0,n-2) {
hijos[H[i][0]+1].push_back({H[i][1]+1, L[i]});
hijos[H[i][1]+1].push_back({H[i][0]+1, L[i]});
}
cola.push(1);
while(!cola.empty()){
act = cola.front();
cola.pop();
dfs(act,0); //obtengo el centroide
mitad = tam[act]/2;
padre = 0;
do{
cond = false;
for(auto h : hijos[act]) {
if (h.des == padre || vis[h.des] == 1 || tam[h.des] <= mitad) continue;
padre = act;
act = h.des;
cond = true;
break;
}
}while(cond);
solve(act);
vis[act] = 1;
for(auto h : hijos[act]) {
if (vis[h.des] == 1) continue;
cola.push(h.des);
}
}
return res;
}
