#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; }