#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll best_path(ll n,ll k,ll h[][2],ll l[])
{
ll inf=3e18+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)
{
mn[0]=0;
return;
}
if(!mn[w])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<vector<pair<ll, ll>>> ancestors(n+1);
function<void(ll, ll, ll, ll,ll)> dfs = [&](ll node,ll par,ll cent,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,cent, cur_depth +1,cost+z);
}
ancestors[node].emplace_back(cost,cur_depth);
};
function<void(ll)> build_decomp = [&](ll node)
{
ll c = get_centroid(node, -1, get_sz(node, -1));
/// Conquer
for (auto[next,z]:adj[c])
{
if (is_removed[next]) continue;
dfs(next, c, c, 1,z);
// node par cent depth
for(auto [w,len]:ancestors[next])
ans=min(ans,len+get_mn(k-w));
for(auto [w,len]:ancestors[next])
add(w,len);
}
/// Divide :
is_removed[c] = 1;
mn.clear();
for (auto[next,z]:adj[c])
{
if (is_removed[next]) continue;
build_decomp(next);
}
};
build_decomp(1);
if(ans==inf)ans=-1;
return ans;
}
//signed main()
//{
// ios::sync_with_stdio(0),cin.tie(0);
//
// ll n,k;
// cin>>n>>k;
// ll 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
