#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 10, M = 1e6 + 10;
vector<pair<int, long long>> adj[NN];
map<long long, int>mn;
int sz[NN];
bool marked[NN];
int ans = NN;
long long D;
void dfs_sz(int node, int parent){
sz[node] = 1;
for(auto [u, w]: adj[node]){
if(u == parent || marked[u]) continue;
dfs_sz(u, node);
sz[node] += sz[u];
}
}
int centroid(int node, int parent, int s){
for(auto [u, w] : adj[node]){
if(u == parent || marked[u]) continue;
if(sz[u] > s / 2) return centroid(u, node, s);
}
return node;
}
long long mx;
void dfs1(int node, int parent, int cnt, long long d){
if(d > D) return;
if(mn.find(D - d) != mn.end()){
ans = min(ans, mn[D - d] + cnt);
}
for(auto [u, w] : adj[node]){
if(marked[u] || u == parent) continue;
dfs1(u, node, cnt + 1, d + w);
}
}
void dfs2(int node, int parent, int cnt, long long d){
if(d > D) return;
if(mn.find(d) == mn.end()) mn[d] = cnt;
else mn[d] = min(mn[d], cnt);
for(auto [u, w] : adj[node]){
if(marked[u] || u == parent) continue;
dfs2(u, node, cnt + 1, d + w);
}
}
void decompose(int node){
dfs_sz(node, 0);
int c = centroid(node, 0, sz[node]);
marked[c] = 1;
mn[0] = 0;
for(auto [u, w] : adj[c]){
if(marked[u]) continue;
dfs1(u, c, 1, w);
dfs2(u, c, 1, w);
}
mn.clear();
for(auto [i, w] : adj[c]){
if(marked[i]) continue;
decompose(i);
}
}
int best_path(int n, int K, int H[][2], int L[]) {
D = 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] });
}
for(int i = 1; i < M; i++){
mn[i] = NN;
}
decompose(1);
return (ans == NN ? -1 : ans);
}
