#include <bits/stdc++.h>
#include "race.h"
using namespace std;
int k, n;
vector<pair<int, int>> g[200005];
int ans = 1e9, dp[200005][105];
void dfs(int u, int par) {
for(int i = 0; i <= k; i++) dp[u][i] = 1e9;
dp[u][0] = 0;
for(auto v: g[u]) {
if(v.first == par) continue;
dfs(v.first, u);
for(int j = 0; j <= k - v.second; j++)
ans = min(ans, dp[v.first][k - j - v.second] + 1 + dp[u][j]);
for(int j = v.second; j <= k; j++)
dp[u][j] = min(dp[u][j], dp[v.first][j - v.second]+1);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for(int i =0; i < n-1; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
dfs(0, -1);
if(ans == 1e9) return -1;
return ans;
}
