#include <bits/stdc++.h> #include "race.h" using namespace std; typedef long long ll; const int max_n = 200000; vector<pair<int,int>> g[max_n]; bool vis[max_n]; bool done[max_n]; int ans = INT_MAX; void dfs(int u, int k, ll dist = 0, int length = 0) { if (dist == k) { ans = min(ans, length); return; } if (dist > k || length >= ans) return; vis[u] = true; for (auto [v, l] : g[u]) if (!vis[v] && !done[v]) dfs(v, k, dist + l, length + 1); } int best_path(int N, int K, int H[][2], int L[]) { 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]}); } memset(done, false, sizeof(done)); for (int i = 0; i < N; i++) { memset(vis, false, sizeof(vis)); dfs(i, K); done[i] = true; } return (ans == INT_MAX ? -1 : ans); }