#include "race.h" #include <bits/stdc++.h> using namespace std; const int mxn = 2e5 + 5; vector<pair<int, int>> adj[mxn]; int del[mxn], sz[mxn]; map<int, int> mp; vector<pair<int, int>> tmp; int res = 2e9; void dfs(int x, int par = -1) { sz[x] = 1; for (auto [w, p] : adj[x]) { if (p == par || del[p]) continue; dfs(p, x); sz[x] += sz[p]; } } int centroid(int x, int n, int par = -1) { for (auto [w, p] : adj[x]) { if (p == par || del[p]) continue; if (sz[p] * 2 > n) return centroid(p, n, x); } return x; } void dfs2(int k, int x, int par, int dis, int cnt) { if (dis > k) return; tmp.push_back({dis, cnt}); if (mp.find(k - dis) != mp.end()) res = min(res, mp[k - dis] + cnt); for (auto [w, p] : adj[x]) { if (p == par || del[p]) continue; dfs2(k, p, x, dis + w, cnt + 1); } } void solve(int k, int x) { dfs(x); int c = centroid(x, sz[x]); mp.clear(), tmp.clear(); mp[0] = 0; for (auto [w, i] : adj[c]) { if (!del[i]) { dfs2(k, i, c, w, 1); for (auto [d, c] : tmp) { if (mp.find(d) == mp.end()) mp[d] = c; else mp[d] = min(mp[d], c); } tmp.clear(); } } del[c] = 1; for (auto [w, i] : adj[c]) { if (!del[i]) solve(k, i); } } 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({L[i], H[i][1]}); adj[H[i][1]].push_back({L[i], H[i][0]}); } solve(K, 0); if (res == 2e9) return -1; return res; }