#include<bits/stdc++.h>
#include "race.h"
#define ll long long
using namespace std;
const int maxK = (int)1e6 + 5;
struct Undirected_Graph{
int N, K, ans = (int)1e9;
vector<vector<pair<int,int>>>adj;
vector<int>Used;
vector<int>Sz;
ll dp[maxK];
vector<int>vec;
Undirected_Graph(int _N, int _K, int H[0][2], int L[]):N(_N),K(_K){
adj.resize(N);
Used.resize(N);
for (int i = 0; i <= K; i++){
dp[i] = (int)1e9;
}
Sz.resize(N);
for (int i = 0; i < N - 1; i++){
adj[H[i][1]].push_back({H[i][0], L[i]});
adj[H[i][0]].push_back({H[i][1], L[i]});
}
}
int Make(int U, int P){
Sz[U] = 1;
for (auto [f,w] : adj[U]){
if (f == P || Used[f])continue;
Sz[U] += Make(f,U);
}
return Sz[U];
}
int Who(int U, int P, int Des){
for (auto [f,w] : adj[U]){
if (f == P || Used[f])continue;
if (Sz[f] * 2 > Des)return Who(f,U,Des);
}
return U;
}
void put(int u, int p, int depth, int orz){
if (depth > K)return;
vec.push_back(depth);
dp[depth] = min(dp[depth], (ll)orz);
for (auto [f,w] : adj[u]){
if (f == p || Used[f])continue;
put(f,u,depth+w,orz+1);
}
}
void Dfs(int u, int p, int depth, int orz){
if (depth > K)return;
ans = min((ll)ans, dp[K - depth] + orz);
for (auto [f,w] : adj[u]){
if (f == p || Used[f])continue;
Dfs(f,u,depth+w,orz+1);
}
}
void Centroid_Decomposition(int U, int P){
int Centroid = Who(U,P, Make(U,P));
for (auto val : vec){
dp[val] = (int)1e9;
}
vec.clear();
dp[0] = 0;
for (auto [f,w] : adj[Centroid]){
if (Used[f] || f == P)continue;
Dfs(f,Centroid,w,1);
put(f,Centroid,w,1);
}
Used[Centroid] = 1;
for (auto [f,w] : adj[Centroid]){
if (Used[f] || f == P)continue;
Centroid_Decomposition(f,Centroid);
}
}
};
int best_path(int N, int K, int H[][2], int L[])
{
Undirected_Graph G(N,K,H,L);
G.Centroid_Decomposition(0,-1);
return (G.ans == (int)1e9 ? -1 : G.ans);
}
