#include "race.h" #include "bits/stdc++.h" using namespace std; const int MXN = 2e5 + 5; const int MXK = 105; const int MXV = 1e7 + 5; vector<pair<int, int>> adj[MXN]; int dp[MXN][MXK]; void dfs(int u, int p) { dp[u][0] = 0; for (auto &[v, w] : adj[u]) { if (v == p) { continue; } for (int i = MXK - 1; i >= w; --i) { if (dp[u][i - w] != MXV) { dp[v][i] = min(dp[v][i], dp[u][i - w] + 1); } } dfs(v, u); } } int best_path(int N, int K, int H[][2], int L[]) { 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 = 0; i < N; ++i) { for (int j = 0; j <= K; ++j) { dp[i][j] = MXV; } } dfs(0, -1); int ans = MXV; for (int i = 0; i < N; ++i) { if (dp[i][K] != MXV) { ans = min(ans, dp[i][K]); } } return (ans == MXV ? -1 : ans); }