#include<bits/stdc++.h> #define ll long long #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) using namespace std; const int N=2e5+5,K=1005; vector<array<int,2>>g[N]; int n,k,ans=1e9,mn[N][K]; void dfs(int u,int p){ mn[u][0]=0; for(auto[v,w]:g[u]){ if(v==p)continue; dfs(v,u); for(int i=0;i<=k;i++){ if(mn[u][i]<1e9){ int need=k-i; if(w<=need&&mn[v][need-w]<1e9)ans=min(ans,mn[u][i]+mn[v][need-w]+1); } } for(int i=0;i+w<=k;i++)if(mn[v][i]<1e9)mn[u][i+w]=min(mn[u][i+w],mn[v][i]+1); } } int best_path(int n_,int k_,int h[][2],int *l){ n=n_,k=k_; for(int i=0;i<n;i++)for(int j=0;j<=k;j++)mn[i][j]=1e9; 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]}); dfs(0,-1); return ans==1e9?-1:ans; }