#include "race.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll, ll> #define fi first #define sec second const int MAXN = 2e5; const ll INF = 1e18; vector <pii> adj[MAXN + 5]; ll ans = INF, N, K, vis[MAXN + 5], sz[MAXN + 5]; void dfs(ll idx, ll par) { sz[idx] = 1; for (auto [i, j] : adj[idx]) { if (i != par && !vis[i]) { dfs(i, idx); sz[idx] += sz[i]; } } } ll find_centroid(ll idx, ll par, ll cur_sz) { for (auto [i, j] : adj[idx]) { if (i != par && !vis[i]) { if (sz[i] > cur_sz / 2) return find_centroid(i, idx, cur_sz); } } return idx; } vector <ll> v; ll dist[MAXN + 5], dist2[MAXN + 5]; map<ll, ll> mp; void dfs2(ll idx, ll par) { v.push_back(idx); for (auto [i, j] : adj[idx]) { if (i != par && !vis[i]) { dist[i] = dist[idx] + j; dist2[i] = dist2[idx] + 1; dfs2(i, idx); } } } void solve(ll idx) { dfs(idx, -1); ll cen = find_centroid(idx, -1, sz[idx]); vis[cen] = 1; dist[cen] = dist2[cen] = 0; for (auto [i, j] : adj[cen]) { if (!vis[i]) { dist[i] = dist[cen] + j; dist2[i] = dist2[cen] + 1; v.clear(); dfs2(i, cen); for (auto x : v) { if (mp.count(K - dist[x])) { ans = min(ans, dist2[x] + mp[K - dist[x]]); } } for (auto x : v) { if (!mp.count(dist[x])) mp[dist[x]] = dist2[x]; else mp[dist[x]] = min(mp[dist[x]], dist2[x]); } } } if (mp.count(K)) { ans = min(ans, mp[K]); } mp.clear(); for (auto [i, j] : adj[cen]) { if (!vis[i]) solve(i); } } int best_path(int n, int k, int H[][2], int L[]) { N = n, K = k; 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]}); } solve(0); if (ans == INF) ans = -1; return ans; }