#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 1e9 + 7;
int depth[maxn];
int road[maxn];
int n, k;
vector<pair<int, int>> tr[maxn];
struct Node{
int index, depth, road;
int parent;
Node(){}
Node(int _index, int _depth, int _road, int _parent) : index(_index), depth(_depth), road(_road), parent(_parent) {}
bool operator>(const Node &other) const{
if(depth != other.depth) return depth > other.depth;
else if(road != other.road){
if(road <= k && other.road <= k) return road < other.road;
else if(road <= k) return false;
else if(other.road <= k) return true;
else return road > other.road;
}
return index > other.index;
}
};
void dfs(int u, int p){
for(auto node : tr[u]){
int v = node.first;
int w = node.second;
if(v == p) continue;
depth[v] = depth[u] + 1;
road[v] = road[u] + w;
dfs(v, u);
}
}
int bfs(int u){
priority_queue<Node, vector<Node>, greater<Node>> q;
q.push({u, 0, 0, -1});
while(!q.empty()){
Node first = q.top();
q.pop();
int u = first.index;
int cur = first.road;
if(cur == k){
return first.depth;
}
for(auto node : tr[u]){
int v = node.first;
int w = node.second;
if(v == first.parent) continue;
q.push({v, first.depth + 1, cur + w, u});
}
}
return inf;
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
for(int i = 0; i < n - 1; i++){
int a, b, l;
a = H[i][0];
b = H[i][1];
l = L[i];
tr[a].push_back({b, l});
tr[b].push_back({a, l});
}
int result = inf;
if(k <= 100){
for(int i = 0; i < n; i++){
int temp = bfs(i);
result = min(result, temp);
}
}else{
for(int i = 0; i < n; i++){
depth[i] = 0;
road[i] = 0;
dfs(i, -1);
for(int j = 0; j < n; j++){
if(road[j] == k && result > depth[j]){
result = depth[j];
}
}
}
}
if(result == inf){
return -1;
}else{
return result;
}
}
