#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 18
#define MAXN 1000005
vector<vector<pair<int,int>>> graph;
vector<int> sz, marked;
map<int,int> mp;
int req_len;
int ans = 1e8;
int get_sz(int node, int parent) {
sz[node] = 1;
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f])
sz[node] += get_sz(u.f, node);
}
return sz[node];
}
int find_centro(int node, int parent, int n) {
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f] && sz[u.f] * 2 >= n)
return find_centro(u.f, node, n);
}
return node;
}
void eval(int node, int parent, int dist, int edges) {
if (dist > req_len)
return ;
if (req_len-dist == 0)
ans = min(ans, edges);
else if (req_len-dist != 0 && mp[req_len-dist] != 0)
ans = min(ans, mp[req_len - dist] + edges);
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f])
eval(u.f, node, dist + u.s, edges + 1);
}
}
void add(int node, int parent, int dist, int edges) {
if (dist > req_len)
return ;
if (mp[dist] == 0)
mp[dist] = edges;
else
mp[dist] = min(mp[dist], edges);
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f])
add(u.f, node, dist + u.s, edges + 1);
}
}
void solve(int node, int parent) {
int n = get_sz(node, parent);
int centro = find_centro(node, parent, n);
marked[centro] = true;
mp = map<int,int>();
for (auto u : graph[centro]) {
if (!marked[u.f]) {
eval(u.f, centro, u.s, 1);
add(u.f, centro, u.s, 1);
}
}
for (auto u : graph[centro]) {
if (u.f != parent && !marked[u.f])
solve(u.f, centro);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
req_len = K;
graph = vector<vector<pair<int,int>>>(N, vector<pair<int,int>>());
sz = vector<int>(N);
marked = vector<int>(N, false);
for (int i = 0; i < N-1; i++) {
graph[H[i][0]].push_back({H[i][1], L[i]});
graph[H[i][1]].push_back({H[i][0], L[i]});
}
solve(0, 0);
if (ans >= 1e8)
return -1;
else
return ans;
}
