#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;
int best_path(int n, int k, int h[][2], int l[]){
vector<int> check(n,0);
matrix<pii> grafo(n);
for(int i = 0; i < n-1; i++)
grafo[h[i][0]].push_back({h[i][1],l[i]}), grafo[h[i][1]].push_back({h[i][0],l[i]});
int centroid;
function<int(int,int,int)> dfsc = [&](int id, int last, int sizee){
int ret = 1, maxi = 0;
for(int i = 0; i < grafo[id].size(); i++){
pii viz = grafo[id][i];
if(viz.ff == last || check[viz.ff])
continue;
int cur = dfsc(viz.ff,id,sizee);
ret+=cur;
maxi = max(maxi,cur);
}
maxi = max(maxi,sizee-ret);
if(maxi <= sizee/2)
centroid = id;
return ret;
};
function<int(int,int,int,int,vector<pii>&v)> dfsd = [&](int id, int last, int ct, int dist, vector<pii>&v){
if(dist > 1e7)
dist = 1e7;
v.push_back({ct,dist});
int ret = 1;
for(int i = 0; i < grafo[id].size(); i++){
pii viz = grafo[id][i];
if(viz.ff == last || check[viz.ff])
continue;
ret+=dfsd(viz.ff,id,ct+1,dist+viz.ss,v);
}
return ret;
};
int resp = INF;
function<void(int,int)> findcentroid = [&](int id, int sizee){
dfsc(id,-1,sizee);
int curc = centroid;
check[curc] = 1;
map<int,int> m;
for(int i = 0; i < grafo[curc].size(); i++){
if(check[grafo[curc][i].ff])
continue;
vector<pii> dlist;
int subtree = dfsd(grafo[curc][i].ff,-1,1,grafo[curc][i].ss,dlist);
for(pii j : dlist){
if(m.count(k-j.ss))
resp = min(resp,m[k-j.ss]+j.ff);
}
for(pii j : dlist){
if(m.count(j.ss))
m[j.ss] = min(m[j.ss],j.ff);
else m[j.ss] = j.ff;
}
findcentroid(grafo[curc][i].ff,subtree);
}
if(m.count(k))
resp = min(resp,m[k]);
};
findcentroid(0,n);
if(resp == INF)
return -1;
return resp;
}
