#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=1e6+5; vector<array<int,2>>g[N]; int n,k,ans=1e9,sz[N],mn[K],del[N]; int dfs_sz(int u,int p){ sz[u]=1; for(auto[v,w]:g[u])if(v!=p&&!del[v])sz[u]+=dfs_sz(v,u); return sz[u]; } int centroid(int u,int p,int tot){ for(auto[v,w]:g[u])if(v!=p&&!del[v]&&sz[v]*2>tot)return centroid(v,u,tot); return u; } void dfs(int u,int p,int d,int e,vector<array<int,2>>&paths){ if(d>k)return; paths.push_back({d,e}); for(auto [v,w]:g[u])if(v!=p&&!del[v])dfs(v,u,d+w,e+1,paths); } void solve(int u){ int c=centroid(u,-1,dfs_sz(u,-1)); del[c]=1; vector<vector<array<int,2>>>all; for(auto[v,w]:g[c]){ if(del[v])continue; vector<array<int,2>>paths; dfs(v,c,w,1,paths),all.push_back(paths); for(auto[d,e]:paths)if(d<=k)ans=min(ans,mn[k-d]+e); } for(auto&paths:all)for(auto[d,e]:paths)if(d<=k)mn[d]=min(mn[d],e); for(auto&paths:all)for(auto[d,e]:paths)if(d<=k)mn[d]=1e9; for(auto[v,w]:g[c])if(!del[v])solve(v); } int best_path(int n_,int k_,int h[][2],int *l){ n=n_,k=k_,fill(mn,mn+k+1,1e9),mn[0]=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]}); solve(0); return ans==1e9?-1:ans; }