//#pragma once
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 3;
int k;
vector<pair<int,int>>adj[N];
bool marked[N];
int sub[N];
int sz;
int ans = 1e9;
int dfs_subtree(int node, int prev){
sub[node] = 1;
for(auto& edge : adj[node]){
if(edge.first != prev && !marked[edge.first]){
sub[node] += dfs_subtree(edge.first, node);
}
}
return sub[node];
}
int find_centroid(int node, int prev){
for(auto& edge : adj[node]){
if(edge.first != prev && !marked[edge.first] && 2 * sub[edge.first] > sz){
return find_centroid(edge.first, node);
}
}
return node;
}
map<int,int>mp{};
vector<pair<int,int>>vc;
void dfs( int node, int prev, int cur, int len){
if(cur>k)return;
vc.push_back({cur,len});
auto it = mp.find(k - cur);
if(it != mp.end()){
ans = min(ans, it->second+len);
}
for(auto & edge : adj[node]){
if(edge.first != prev && !marked[edge.first]){
dfs(edge.first, node, cur + edge.second, len + 1);
}
}
}
void decompose(int node){
dfs_subtree(node, -1);
sz = sub[node];
int c = find_centroid(node, -1);
mp[0]=0;
for(auto&edge:adj[c]){
int child = edge.first;
if(!marked[child]){
vc.clear();
dfs(child, c, edge.second, 1);
for(auto&p:vc){
auto it = mp.find(p.first);
if(it==mp.end()){
mp[p.first]=p.second;
}else{
it->second=min(it->second, p.second);
}
}
}
}
marked[c] = 1;
mp.clear();
for(auto&edge:adj[c]){
if(!marked[edge.first])decompose(edge.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i = 0; i < N - 1; i++){
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
decompose(0);
if(ans == 1e9) return -1;
return ans;
}
