#include "race.h" #include <bits/stdc++.h> using namespace std; const int maxn = 200005; vector <pair <int, long long> > v[maxn]; long long dist[maxn]; int koraci[maxn]; int ans = 1e9; void dfs2 (int x, int p){ for (int i = 0; i < v[x].size(); i++){ int y = v[x][i].first; int d = v[x][i].second; if (y != p){ dist[y] = dist[x] + d; koraci[y] = koraci[x] + 1; dfs2(y, x); } } } int best_path (int n, int k, int h[maxn][2], int l[maxn]){ for (int i = 0; i < n - 1; i++){ v[h[i][0]].push_back({h[i][1], l[i]}); v[h[i][1]].push_back({h[i][0], l[i]}); } for (int i = 0; i < n; i++){ dist[i] = 0, koraci[i] = 0; dfs2(i, i); for (int j = 0; j < n; j++){ if (dist[j] == k) ans = min(ans, koraci[j]); } } if (ans == 1e9) return -1; else return ans; } /* int main (void){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k, h[maxn][2], l[maxn]; cin >> n >> k; for (int i = 0; i < n - 1; i++) cin >> h[i][0] >> h[i][1] >> l[i]; cout << best_path(n, k, h, l) << endl; return 0; }*/