#include <bits/stdc++.h>
#include "race.h"
using namespace std ;
const int MAX = 2e5 + 10 ;
vector< vector< pair<int , int> > >adj(MAX) ;
int n , k ;
int src ;
int sz[MAX] , mark[MAX] ;
void pre_dfs(int node , int par)
{
sz[node] = 1 ;
for(auto &childd : adj[node])
{
int child = childd.first , w = childd.second ;
if(child == par || mark[child])
continue ;
pre_dfs(child , node) ;
sz[node] += sz[child] ;
}
}
int FindCentroid(int node , int par)
{
for(auto &childd : adj[node])
{
int child = childd.first , w = childd.second ;
if(child == par || mark[child])
continue ;
if(sz[child] > sz[src] / 2)
return FindCentroid(child , node) ;
}
return node ;
}
int ans = 1e9 ;
int val[MAX] , dep[MAX] ;
void dfs(int node , int par , int w , int t)
{
w = min(w , k+1) ;
if(t == 0 && w <= k)
ans = min(ans , val[k-w] + dep[node]) ;
else if(t == 1 && w <= k)
val[w] = min(val[w] , dep[node]) ;
else if(t == 2 && w <= k)
val[w] = 1e9 ;
for(auto &childd : adj[node])
{
int child = childd.first , w2 = childd.second ;
if(mark[child] || child == par)
continue ;
dep[child] = dep[node] + 1 ;
dfs(child , node , w + w2 , t) ;
}
}
void solve(int Src)
{
src = Src ;
pre_dfs(src , -1) ;
int centroid = FindCentroid(src , -1) ;
mark[centroid] = 1 ;
dep[centroid] = 0 , val[0] = 0 ;
for(auto &childd : adj[centroid])
{
int child = childd.first , w = childd.second ;
if(mark[child])
continue ;
dep[child] = 1 ;
dfs(child , centroid , w , 0) ;
dfs(child , centroid , w , 1) ;
}
for(auto &childd : adj[centroid])
{
int child = childd.first , w = childd.second ;
if(mark[child])
continue ;
dfs(child , centroid , w , 2) ;
}
for(auto &childd : adj[centroid])
{
int child = childd.first , w = childd.second ;
if(mark[child])
continue ;
solve(child) ;
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N , k = K ;
for(int i = 0 ; i < n-1 ; ++i)
{
adj[H[i][0]+1].emplace_back(H[i][1]+1 , L[i]) ;
adj[H[i][1]+1].emplace_back(H[i][0]+1 , L[i]) ;
}
for(int i = 0 ; i <= k ; ++i)
val[i] = 1e9 ;
solve(1) ;
if(ans == 1e9)
ans = -1 ;
return ans ;
}
