#include "race.h" #include <bits/stdc++.h> using namespace std; #define vi vector #define int long long vi<vi<pair<int,int>>> g; vi<int> vis, sz, dis(1e6+5); queue<int> rem; const int inf = 1e18; int ans=inf; int dfs(int i, int par){ sz[i]=1; for(auto &[x, val]:g[i]){ if(vis[x] || x==par)continue; sz[i]+=dfs(x, i); } return sz[i]; } int get_cent(int i, int par, int mx){ for(auto &[x, val]:g[i]){ if(vis[x] || x==par)continue; if(sz[x]>mx/2)return get_cent(x, i, mx); } return i; } void search(int u, int par, int k, queue<pair<int,int>> &nw, int d, int w){ if(k<w)return; ans=min(ans, dis[k-w]+d); nw.push({d, w}); for(auto &[x, val]:g[u]){ if(vis[x] || x==par)continue; search(x, u, k, nw, d+1, w+val); } } void get_ans(int u, int p, int k){ int cent=get_cent(u, p, dfs(u, p)); queue<pair<int,int>> nw; dis[0]=0; for(auto &[x, val]:g[cent]){ if(x==p || vis[x])continue; search(x, cent, k, nw, 1, val); while(!nw.empty()){ auto [d, w] = nw.front(); nw.pop(); dis[w]=min(dis[w], d); rem.push(w); } } vis[cent]=1; while(!rem.empty()){ int x=rem.front(); rem.pop(); dis[x]=inf; } for(auto [x, val]:g[u]){ if(vis[x])continue; get_ans(x, cent, k); } } int32_t best_path(int32_t n, int32_t k, int32_t h[][2], int32_t l[]){ for(int i=0; i<=1e6; i++)dis[i]=inf; g.assign(n, {}); vis.assign(n, 0); sz.assign(n+1, 0); 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]}); } get_ans(0, -1, k); if(ans==inf)return -1; else return ans; }