#include<bits/stdc++.h> #define ll int #define pll pair<ll,ll> using namespace std; vector<vector<pll>> e; vector<ll> sz; vector<bool> rem; map<ll,ll> cnt; ll ans=1e9,k; ll getsz(ll u,ll p){ sz[u]=1; for(auto v:e[u]){ if(v.first==p or rem[v.first]==1) continue; sz[u]+=getsz(v.first,u); } return sz[u]; } ll getct(ll u,ll p,ll n){ for(auto v:e[u]){ if(v.first==p or rem[v.first]==1) continue; if(sz[v.first]>n/2) return getct(v.first,u,n); } return u; } void getans(ll u,ll p,ll d,ll l){ if(l>k) return; if(cnt.find(k-l)!=cnt.end()) ans=min(ans,d+cnt[k-l]); for(auto v:e[u]){ if(v.first==p or rem[v.first]==1) continue; getans(v.first,u,d+1,l+v.second); } } void update(ll u,ll p,ll d,ll l){ if(l>k) return; if(cnt[l]>d or cnt[l]==0) cnt[l]=d; for(auto v:e[u]){ if(v.first==p or rem[v.first]==1) continue; update(v.first,u,d+1,l+v.second); } } void decompose(ll u){ getsz(u,u); ll ct=getct(u,u,sz[u]); rem[ct]=1; cnt.clear(); cnt[0]=0; for(auto v:e[ct]){ if(rem[v.first]==1) continue; getans(v.first,u,1,v.second); update(v.first,u,1,v.second); } for(auto v:e[ct]){ if(rem[v.first]==1) continue; decompose(v.first); } } int best_path(int N,int K,int H[][2],int L[]){ ll n=N; k=K; e.resize(n+1); sz.resize(n+1); rem.resize(n+1,0); for(ll i=0; i<n-1; i++){ e[H[i][0]].push_back({H[i][1],L[i]}); e[H[i][1]].push_back({H[i][0],L[i]}); } decompose(0); if(ans==1e9) return -1; else return ans; }