#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define ll long long
#define mkp(a,b) make_pair(a,b)
#define rep(i,a,b) for (int i = a; i < b; i++)
#define rrep(i,a,b) for (int i = a; i >= b; i--)
#define endl '\n'
#define pb push_back
array<int,3> mods = {1000000007,998244353,676767677};
int MD = mods[2];
ll MX_ll = 1e18;
int MX_VL = 2e9;
int GN = 1e5+10;
vector<map<int,int>> sums;
int res = MX_ll;
vector<int> smdist;
vector<int> dist;
void dfs(vector<vector<pair<int,int>>>& TREE,int ind,int par,int& k) {
sums[ind][smdist[ind]] = dist[ind];
for(auto [child,len]:TREE[ind]) {
if(child==par)continue;
dfs(TREE,child,ind,k);
if(sums[child].size() > sums[ind].size()) {
swap(sums[child],sums[ind]);
sums[ind][smdist[ind]] = dist[ind];
}
for(auto [sum,price]:sums[child]) {
int targ = k+2*smdist[ind]-sum;
if(sums[ind].find(targ)!=sums[ind].end()) {
int cost = price+sums[ind][targ]-2*dist[ind];
res = min(res,cost);
}
if(sums[ind].find(sum)!=sums[ind].end()) {
sums[ind][sum] = min(sums[ind][sum],price);
} else {
sums[ind][sum] = price;
}
}
}
}
void dfs1(vector<vector<pair<int,int>>>& TREE,int ind,int par,int h,int k) {
dist[ind] = k;
smdist[ind] = h;
for(auto [ch,x]:TREE[ind]) {
if(ch==par)continue;
dfs1(TREE,ch,ind,h+x,k+1);
}
}
int best_path(int n,int K,vector<pair<int,int>> edges,vector<int> L) {
vector<vector<pair<int,int>>> TREE(n,vector<pair<int,int>>());
sums.resize(n);
smdist.resize(n);
dist.resize(n);
rep(i,0,n-1) {
TREE[edges[i].first].push_back(mkp(edges[i].second,L[i]));
TREE[edges[i].second].push_back(mkp(edges[i].first,L[i]));
}
dfs1(TREE,0,-1,0,0);
dfs(TREE,0,-1,K);
if(res==MX_ll) return -1;
return res;
}
// signed main()
// {
// int N,K;
// cin>>N>>K;
// vector<pair<int,int>> H(N-1);
// vector<int> L(N-1);
// int ans;
// rep(i,0,N-1) {
// cin>>H[i].first>>H[i].second;
// }
// rep(i,0,N-1) cin>>L[i];
// ans = best_path(N,K,H,L);
// cout<<ans<<endl;
// }
