#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll int
#define endl '\n'
const int N = 2e5 + 5;
vector<pair<ll, ll>> node[N];
ll sz[N];
bool in[N];
ll res = 1e6;
ll K;
map<ll, ll> mem, tmp;
ll initsz(ll u, ll p){
sz[u] = 1;
for (auto j : node[u]){
if (!in[j.first] || j.first == p) continue;
initsz(j.first, u);
sz[u] += sz[j.first];
}
return sz[u];
}
ll CT(ll u, ll p, ll S){
for (auto j : node[u]){
if (!in[j.first] || j.first == p) continue;
if ((sz[j.first] * 2) > S) return CT(j.first, u, S);
}
return u;
}
void addtmp(ll d, ll e){
if (tmp[d] == 0) tmp[d] = e;
else tmp[d] = min(tmp[d], e);
}
void upd(ll d){
if (mem[K - d] != 0) res = min(res, mem[K - d] + tmp[d]);
}
void dfs(ll u, ll p, ll d, ll e){
if (d > K) return;
addtmp(d, e);
upd(d);
for (auto j : node[u]){
if (!in[j.first] || j.first == p) continue;
dfs(j.first, u, d + j.second, e + 1);
}
}
void addmem(ll d, ll e){
if (mem[d] == 0) mem[d] = e;
else mem[d] = min(mem[d], e);
}
void findCT(ll u){
ll S = initsz(u, u);
u = CT(u, u, S);
in[u] = 0;
mem.clear();
for (auto j : node[u]){
if (!in[j.first]) continue;
tmp.clear();
dfs(j.first, j.first, j.second, 1);
if (tmp[K] != 0) res = min(res, tmp[K]);
for (auto j : tmp){
addmem(j.first, j.second);
}
}
for (auto j : node[u]){
if (!in[j.first]) continue;
findCT(j.first);
}
}
ll best_path(int n, int k, int h[][2], int l[]){
for (int i = 1; i < n; i++){
node[h[i - 1][0] + 1].push_back({h[i - 1][1] + 1, l[i - 1]});
node[h[i - 1][1] + 1].push_back({h[i - 1][0] + 1, l[i - 1]});
}
K = k;
memset(in, 1, sizeof(in));
findCT(1);
if (res == 1e6) return -1;
else return res;
}
/*
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("VietCT.INP", "r")){
freopen("VietCT.INP", "r", stdin);
freopen("VietCT.OUT", "w", stdout);
}
}
/*
*/
