#include<bits/stdc++.h>
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
vector<vector<pair<ll,int>>>g;
vector<bool>dead;
vector<int>sz;
int ans=INT_MAX;
void dfs_sz(int u,int p){
sz[u]=1;
for(auto[w,v]:g[u])if(v^p&&!dead[v])dfs_sz(v,u),sz[u]+=sz[v];
}
int centroid(int u,int p,int comp){
for(auto[w,v]:g[u])if(v^p&&!dead[v]&&sz[v]>comp/2)return centroid(v,u,comp);
return u;
}
map<ll,int>mp;
vector<pair<ll,int>>vals;
void dfs(int u,int p,ll dist,int path){
vals.push_back({dist,path});
for(auto[w,v]:g[u])if(v^p&&!dead[v])dfs(v,u,dist+w,path+1);
}
void solve(int u,ll k){
dfs_sz(u,-1);
int c=centroid(u,-1,sz[u]);
mp[0]=0;
for(auto[w,v]:g[c]){
if(dead[v])continue;
dfs(v,c,w,1);
for(auto x:vals)if(mp.count(k-x.first))ans=min(ans,x.second+mp[k-x.first]);
for(auto x:vals){
if(!mp.count(x.first))mp[x.first]=x.second;
else mp[x.first]=min(mp[x.first],x.second);
}
vals.clear();
}
mp.clear(),dead[c]=1;
for(auto[w,v]:g[c])if(!dead[v])solve(v,k);
}
int best_path(int n,int k,int h[][2],int *l){
g=vector<vector<pair<ll,int>>>(n);
dead=vector<bool>(n);
sz=vector<int>(n);
for(int i=0;i<n-1;i++)g[h[i][0]].push_back({l[i],h[i][1]}),g[h[i][1]].push_back({l[i],h[i][0]});
solve(0,k);
int res=ans;
g.clear(),dead.clear(),sz.clear(),ans=INT_MAX;
return res!=INT_MAX?res:-1;
}
