#include <bits/stdc++.h>
#include "race.h"
#define DIMN 200010
#define MAX_N 500000
using namespace std;
vector < pair <int,int> > v[DIMN];
set < pair <long long,int> > per[DIMN];
int sub[DIMN] , f[DIMN] , distanta[DIMN];
long long add[DIMN];
int sol;
void precalc (int nod , int tt){
int i , vecin;
sub[nod] = 1;
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
if (vecin != tt && !f[vecin]){
precalc (vecin , nod);
sub[nod] += sub[vecin];
}
}
}
void dfs (int nod , int tt , int k){
int i , vecin , maxi = 0 , fiu ;
long long rms;
set < pair <long long,int> > :: iterator aux;
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
if (vecin != tt && sub[vecin] > maxi){
maxi = sub[vecin];
fiu = vecin;
}
}
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
if (vecin != tt){
dfs (vecin , nod , k);
add[vecin] += v[nod][i].second;
distanta[vecin]++;
}
}
if (maxi){
per[nod].swap(per[fiu]);
add[nod] = add[fiu];
distanta[nod] = distanta[fiu];
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
if (vecin != tt){
if (vecin != fiu){
rms = k - v[nod][i].second - add[nod];
aux = per[nod].upper_bound(make_pair(rms , -2000000000));
if (aux != per[nod].end() && aux->first == rms){
sol = min(sol , 1 + aux->second + distanta[nod]);
}
}
per[nod].insert(make_pair(v[nod][i].second - add[nod] , 1 - distanta[nod]));
}
if (vecin != tt && vecin != fiu){
/// sa zicem ca nod ar fi lca - ul , un capat pana acum , unul in vecin
for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){
if (it->first + add[vecin] > k)
continue;
rms = k - (it->first + add[vecin]) - add[nod];
aux = per[nod].upper_bound(make_pair(rms , -2000000000));
if (aux != per[nod].end() && aux->first == rms){
sol = min(sol , it->second + distanta[vecin] + aux->second + distanta[nod]);
}
}
/// vezi cum le unesti
for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){
if (it->first + add[vecin] > k)
continue; /// nu imi pasa
per[nod].insert(make_pair(it->first + add[vecin] - add[nod] , it->second + distanta[vecin] - distanta[nod]));
}
}
}
}
aux = per[nod].upper_bound(make_pair(k - add[nod] , -2000000000));
if (aux != per[nod].end() && aux->first == k - add[nod]){
sol = min(sol , aux->second + distanta[nod]);
}
}
int best_path(int n, int k, int h[][2], int l[]){
int i;
for (i = 0 ; i < n - 1 ; i++){
h[i][1]++;
h[i][0]++;
v[h[i][0]].push_back(make_pair(h[i][1] , l[i]));
v[h[i][1]].push_back(make_pair(h[i][0] , l[i]));
}
precalc (1 , 0);
sol = 2000000000;
dfs (1 , 0 , k);
return (sol == 2000000000 ? -1 : sol);
}
