#include <iostream>
#include <unordered_map>
#include <vector>
using ll = long long;
using namespace std;
const int MAXN = 2e5 + 7;
vector<pair<int, int>> graf[MAXN];
bool zablokowane[MAXN];
int rozmiarPoddrzewa[MAXN];
ll k;
void PoliczWielkoscPoddrzew(int v, int p){
rozmiarPoddrzewa[v] = 1;
for (auto& [s, w] : graf[v]){
if (!zablokowane[s] && s != p){
PoliczWielkoscPoddrzew(s, v);
rozmiarPoddrzewa[v] += rozmiarPoddrzewa[s];
}
}
}
int znajdzCentorid(int v, int p, int calaWielkosc){
int maksPoddrzewo = 0;
for (auto& [s, w] : graf[v]){
if (!zablokowane[s] && s != p){
maksPoddrzewo = max(maksPoddrzewo, rozmiarPoddrzewa[s] - 1);
int kan = znajdzCentorid(s, v, calaWielkosc);
if (kan != -1) return kan;
}
if (!zablokowane[s] && s == p){
maksPoddrzewo = max(maksPoddrzewo, calaWielkosc - rozmiarPoddrzewa[v]);
}
}
if (maksPoddrzewo <= calaWielkosc / 2) return v;
return -1;
}
vector<pair<ll, int>> odleglosci;
void policzOdleglosci(int v, int p, ll aktOdl, int g){
odleglosci.push_back({aktOdl, g});
for (auto& [s, w] : graf[v]){
if (s != p && !zablokowane[s]) policzOdleglosci(s, v, aktOdl + w, g + 1);
}
}
int centroidDecomp(int v){
PoliczWielkoscPoddrzew(v, v);
int centr = znajdzCentorid(v, v, rozmiarPoddrzewa[v]);
//cout << v << ' ' << centr << '\n';
zablokowane[centr] = 1;
int wynik = 1e9;
unordered_map<ll, int> bestOdl;
bestOdl[0] = 0;
for (auto& [s, w] : graf[centr]){
if (!zablokowane[s]){
odleglosci.clear();
policzOdleglosci(s, s, w, 1);
for (auto& [odl, gleb] : odleglosci){
if (bestOdl.find(k - odl) != bestOdl.end()) wynik = min(wynik, gleb + bestOdl[k - odl]);
}
for (auto& [odl, gleb] : odleglosci){
if (bestOdl.find(odl) == bestOdl.end()) bestOdl[odl] = gleb;
else bestOdl[odl] = min(bestOdl[odl], gleb);
}
}
}
bestOdl.clear();
for (auto& [s, w] : graf[centr]){
if (!zablokowane[s]){
wynik = min(wynik, centroidDecomp(s));
}
}
return wynik;
}
int best_path(int N, int K, int H[][2] , int L[]){
k = K;
for (int i = 0; i < N - 1; i++){
graf[H[i][0]].push_back({H[i][1], L[i]});
graf[H[i][1]].push_back({H[i][0], L[i]});
}
int w = centroidDecomp(0);
if (w == 1e9) w = -1;
return w;
}
