#include <bits/stdc++.h> using namespace std; int best_path(int n,int k,int h[][2],int l[]) { #define ll long long ll inf=3e16+5e12,ans=inf; vector<vector<pair<ll,ll>>>adj(n+1); for(int i=0; i<n-1; i++) { ll x=h[i][0]; ll y=h[i][1]; ll z=l[i]; adj[y].emplace_back(x,z); adj[x].emplace_back(y,z); } /// Centroid deco : vector<ll>sz(n+1),is_removed(n+1); map<ll,ll>mn;/// mn[weight] = min len that have this weight function<void(ll,ll)> add=[&](ll w,ll len)/// adds to map { if(w<=0) { mn[0]=0; return; } if(mn.find(w)==mn.end())mn[w]=len; mn[w]=min(mn[w],len); return; }; function<ll(ll)> get_mn=[&](ll w) { if(!w)return 0ll; if(w<0||mn.find(w)==mn.end())return inf; return mn[w]; }; function<ll(ll, ll)> get_sz=[&](ll node,ll par) { sz[node]=1; for(auto[next,z]:adj[node]) { if(next==par || is_removed[next])continue; sz[node]+= get_sz(next,node); } return sz[node]; }; function<ll(ll,ll,ll)>get_centroid=[&](ll node,ll par,ll tot_sz) { for(auto[next,z]:adj[node]) { if(next==par || is_removed[next])continue; if(sz[next]*2>tot_sz)return get_centroid(next,node,tot_sz); } return node; }; vector<pair<ll,ll>>path; function<void(ll, ll, ll,ll)> dfs = [&](ll node,ll par,ll cur_depth,ll cost) { if(cur_depth>k)return; for(auto [next,z]:adj[node]) { if(next==par || is_removed[next])continue; dfs(next,node, cur_depth +1,cost+z); } path.emplace_back(cost,cur_depth); }; function<void(ll)> build_decomp = [&](ll node) { ll c = get_centroid(node, -1, get_sz(node, -1)); /// Conquer is_removed[c] = 1; mn.clear(); for (auto[next,z]:adj[c]) { if (is_removed[next]) continue; path.clear(); dfs(next, c, 1,z); // node par dist depth for(auto [w,len]:path) ans=min(ans,len+get_mn(k-w)); for(auto [w,len]:path) add(w,len); } /// Divide : for (auto[next,z]:adj[c]) { if (is_removed[next]) continue; build_decomp(next); } }; build_decomp(1); #undef ll if(ans==inf)ans=-1; return ans; } //signed main() //{ // ios::sync_with_stdio(0),cin.tie(0); // // int n,k; // cin>>n>>k; // int h[n][2],l[n]; // for(int i=0; i<n-1; i++)cin>>h[i][0]>>h[i][1]; // for(int i=0; i<n-1; i++)cin>>l[i]; // // cout<<best_path(n,k,h,l)<<endl; // //} ///End Main