#include "race.h"
#include <bits/stdc++.h>
using namespace std;
// #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--)
array<ll,3> mods = {1000000007,998244353,676767677};
ll MD = mods[2];
ll MX_ll = 1e18;
ll MX_VL = 2e9;
ll GN = 1e5+10;
vector<map<ll,ll>> sums;
ll res = MX_VL;
vector<ll> smdist;
vector<ll> dist;
void dfs(vector<vector<pair<ll,ll>>>& TREE,ll ind,ll par,ll& 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]) {
ll targ = k+2*smdist[ind]-sum;
if(sums[ind].find(targ)!=sums[ind].end()) {
ll 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<ll,ll>>>& TREE,ll ind,ll par,ll h,ll 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,int edges[][2],int L[]) {
ll n = N;
ll k = K;
vector<vector<pair<ll,ll>>> TREE(n,vector<pair<ll,ll>>());
sums.resize(n);
smdist.resize(n);
dist.resize(n);
rep(i,0,n-1) {
TREE[edges[i][0]].push_back(mkp(edges[i][1],L[i]));
TREE[edges[i][1]].push_back(mkp(edges[i][0],L[i]));
}
dfs1(TREE,0,-1,0,0);
dfs(TREE,0,-1,k);
if(res==MX_ll) return -1;
return res;
}
// ll H[200000][2];
// int L[200000];
// signed main()
// {
// int N,K;
// cin>>N>>K;
// int ans;
// rep(i,0,N-1) {
// cin>>H[i][0]>>H[i][1];
// }
// rep(i,0,N-1) cin>>L[i];
// ans = best_path(N,K,H,L);
// cout<<ans<<endl;
// }
