#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#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 debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define LIM 1000000000000
#define MAX 200000
#define des first
#define val second
lli n,k,a,b,c,res;
lli inval[MAX+2],sub[MAX+2];
vector< pair<lli,lli> > hijos[MAX+2];
set<pair<lli,lli> >::iterator it,ot;
lli inicia(lli pos, lli padre) {
sub[pos] = 0;
for (auto h : hijos[pos]) {
if (h.des == padre) continue;
if (inval[h.des] == 1) continue;
sub[pos] += inicia(h.des,pos);
}
return sub[pos]+1;
}
lli busca(lli pos,lli padre, lli mitad) {
for (auto h : hijos[pos]) {
if (h.des == padre) continue;
if (inval[h.des] == 1) continue;
if (sub[h.des] > mitad) return busca(h.des,pos,mitad);
}
return pos;
}
void llena(lli pos, lli padre, lli cant, lli sum, set<pair<lli,lli> > &act) {
if (sum > k) return;
it = act.lower_bound({sum,0});
if (it == act.end()) act.insert({sum,cant});
else if ((*it).first != sum) act.insert({sum,cant});
else if ((*it).second > cant) {
act.erase(it);
act.insert({sum,cant});
}
for (auto h : hijos[pos]) {
if (h.des == padre) continue;
if (inval[h.des] == 1) continue;
llena(h.des,pos,cant+1,sum+h.val,act);
}
}
void solve(lli pos, lli tam) {
a = inicia(pos,-1);
lli centro = busca(pos,-1,tam/2);
set<pair<lli,lli> > op;
for (auto h : hijos[pos]) {
if (inval[h.des] == 1) continue;
set<pair<lli,lli> > act;
llena(h.des,pos,1,h.val,act);
it = act.begin();
while (it != act.end()) {
a = k - (*it).first;
b = (*it).second;
it++;
ot = op.lower_bound({a,0});
if (ot == op.end()) continue;
if ((*ot).first != a) continue;
b += (*ot).second;
res = min(res,b);
}
it = act.begin();
while (it != act.end()) {
a = (*it).first;
b = (*it).second;
it++;
ot = op.lower_bound({a,0});
if (ot != op.end() && (*ot).first == a){
if ((*ot).second <= b) continue;
op.erase(ot);
}
op.insert({a,b});
}
}
ot = op.lower_bound({k,0});
if (ot != op.end()) res = min(res,(*ot).second);
inval[pos] = 1;
vector<pair<lli,lli> > sig;
for (auto h : hijos[pos]) {
if (inval[h.des] == 1) continue;
sig.push_back({h.des, sub[h.des]});
}
for (auto s : sig) solve(s.first,s.second);
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
rep(i,0,n-2) {
a = H[i][0];
b = H[i][1];
c = L[i];
hijos[a].push_back({b,c});
hijos[b].push_back({a,c});
}
res = LIM;
solve(0,n);
if (res == LIM) return -1;
else return res;
}
