#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
const int MAX = 1e6;
vector<pair<int, int>> graph[MAXN+1];
int sz[MAXN+1];
bitset<MAXN+1> usd;
int find_centroid(int root){
function<void(int, int)> get_sz = [&](int v, int p){
sz[v] = 1;
for(auto [u, d] : graph[v]){
if(usd[u] || u == p) continue;
get_sz(u, v);
sz[v] += sz[u];
}
};
get_sz(root, -1);
function<int(int, int)> dfs = [&](int v, int p){
for(auto [u, d] : graph[v]){
if(usd[u] || u == p) continue;
if(sz[u] > sz[root]/2) return dfs(u, v);
}
return v;
};
return dfs(root, -1);
}
tuple<int, int, int, int> best[MAX+1];//best and second best edges to reach dist
int TRACK;// K
int ANS; // answer
void update(const int &root, int v, int p, int dist, int lvl){
if(dist > TRACK) return;
//update best values
auto [l1, u1, l2, u2] = best[dist];
if(l1 != -1 && l2 != -1){
if(lvl < l1){
if(root == u1){
l1 = lvl, u1 = root;
}
else{
l2 = l1, u2 = l2;
l1 = lvl, u1 = root;
}
}
else if(lvl < l2){
if(root == u1){
}
else{
l2 = lvl, u2 = root;
}
}
}
else if(l1 == -1){
l1 = lvl, u1 = root;
}
else if(l2 == -1){
if(lvl < l1){
if(root == u1){
l1 = lvl, u1 = root;
}
else{
l2 = l1, u2 = u1;
l1 = lvl, u1 = root;
}
}
}
best[dist] = {l1, u1, l2, u2};
for(auto [u, d] : graph[v]){
if(usd[u] || u == p) continue;
update(root, u, v, dist + d, lvl+1);
}
}
void calc(const int &root, int v, int p, int dist, int lvl){
if(dist > TRACK) return;
auto [l1, u1, l2, u2] = best[TRACK - dist];
if(l1 != -1 && root != u1){
ANS = min(ANS, l1 + lvl);
}
else if(l2 != -1){
ANS = min(ANS, l2 + lvl);
}
for(auto [u, d] : graph[v]){
if(usd[u] || u == p) continue;
calc(root, u, v, dist + d, lvl + 1);
}
}
void clear(int v, int p, int dist){
if(dist > TRACK) return;
best[dist] = {-1, -1, -1, -1};
for(auto [u, d] : graph[v]){
if(usd[u] || u == p) continue;
clear(u, v, dist + d);
}
}
void centroid_decomposition(int root){
function<void(int)> dfs = [&](int v){
int c = find_centroid(v);
usd[c] = 1;
for(auto [u, d] : graph[c]){
if(usd[u]) continue;
dfs(u);
}
for(auto [u, d] : graph[c]){
if(usd[u]) continue;
update(u, u, c, d, 1);
}
if(get<0>(best[TRACK]) != -1){
ANS = min(ANS, get<0>(best[TRACK]));
}
for(auto [u, d] : graph[c]){
if(usd[u]) continue;
calc(u, u, c, d, 1);
}
clear(c, -1, 0);
usd[c] = 0;
};
dfs(root);
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i=0; i<N-1; i++){
graph[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
graph[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
}
TRACK = K;
for(int i=0; i<=MAX; i++){
best[i] = {-1, -1, -1, -1};
}
ANS = N;
centroid_decomposition(1);
return (ANS == N ? -1 : ANS);
}
