#include "race.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
#include <queue>
#include <time.h>
#include <bitset>
#include <unordered_map>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ft first
#define sc second
#define add push_back
#define all(v) v.begin(),v.end()
#define mpr make_pair
#define sz(v) (ll)v.size()
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)
#define FORD(i,a,b) for(ll i = (a); i >= (b); i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const ll MOD = 1e9+7;
const ll INF = 1e9;
const int N = 200005;
vector<pll> g[N];
ll answ = -1;
ll entsize[N];
bool used[N];
ll nn = 0;
ll k;
void dfs_sz(int u, int p)
{
nn++;
entsize[u] = 1;
for(auto f : g[u])
{
if(f.ft == p or used[f.ft])
{
continue;
}
dfs_sz(f.ft,u);
entsize[u]+=entsize[f.ft];
}
}
int find_center(int u, int p)
{
int mx_size = -1;
int vert = -1;
for(auto f : g[u])
{
if(f.ft == p or used[f.ft])
{
continue;
}
if(entsize[f.ft] > mx_size)
{
mx_size = entsize[f.ft];
vert = f.ft;
}
}
if(2*mx_size <= nn)
{
return u;
}
return find_center(vert,u);
}
int find_centroid(int u)
{
nn = 0;
dfs_sz(u,u);
return find_center(u,u);
}
vector<pll> mas;
map<ll,ll> mp;
void update(ll o)
{
if(answ == -1 or o < answ)
{
answ = o;
}
}
void solve(int u, int p, int dist, int depth)
{
if(p != u)
{
mas.add(mpr(dist,depth));
}
for(auto f : g[u])
{
if(f.ft == p or used[f.ft])
{
continue;
}
solve(f.ft,u,dist+f.sc,depth+1);
if(p == u)
{
for(auto hg : mas)
{
if(hg.ft > k)
{
continue;
}
else if(hg.ft == k)
{
update(hg.sc);
}
else
{
if(mp.find(k-hg.ft) != mp.end())
{
update(mp[k-hg.ft] + hg.sc);
}
}
}
for(auto hg : mas)
{
if(hg.ft > k)
{
continue;
}
if(mp.find(hg.ft) == mp.end())
{
mp[hg.ft] = hg.sc;
}
else
{
mp[hg.ft] = min(mp[hg.ft], hg.sc);
}
}
mas.clear();
}
}
}
void centroid_decomposition()
{
queue<ll> q;
q.push(1);
while(!q.empty())
{
int vnow = q.front();
q.pop();
mp.clear();
int cen = find_centroid(vnow);
solve(cen,cen,0,0);
used[vnow] = 1;
for(auto f : g[vnow])
{
if(used[f.ft])
{
continue;
}
q.push(f.ft);
}
}
}
int best_path(int n, int K, int H[][2], int L[])
{
k = K;
FOR(i,0,n-1)
{
g[H[i][0]].add(mpr(H[i][1],L[i]));
g[H[i][1]].add(mpr(H[i][0],L[i]));
}
centroid_decomposition();
return answ;
}
// int main()
// {
// // int l[] = {3,4,5,4,6,3,2,5,6,7};
// // int h[][2] = {{0,1}, {0,2}, {2,3}, {3,4}, {4,5}, {0,6}, {6,7}, {6,8}, {8,9}, {8,10}};
// int l[] = {1,1};
// int h[][2] = {{0,1},{1,2}};
// cout<<best_path(3,3,h,l)<<endl;
// return 0;
// }
/*
░▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░
▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒
▓▓▓▒░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▒░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▒░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▒░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░▒▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▒░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░░░▒▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▒░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▒░░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▒░▒▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▒░░▒▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▒░░░░░▒▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░░▒▓▓▓▓▓
▓▓▓▓▓▒░░░░░░░░▒▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░░▒▓▓▓
▓▓▓▓▒░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░▒▓▓
▓▓▓▓▓▒░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░▒▓▓▓
▓▓▓▓▓▓▒░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░▒▓▓▓▓
▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒
░▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░
⠀⠀⠀⠀⠀
*/
