#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)2e5 + 9;
vector<pii> T[N];
bool use[N];
int subt[N];
int dist[N];
void dfs1(int u, int par){
subt[u] = 1;
for(auto x : T[u]){
if(x.fi == par)
continue;
dfs1(x.fi, u);
subt[u] += subt[x.fi];
}
}
int K;
int res = -1;
vector<pii> tti;
void dfs2(int u, int par, int cent, int dd, int ln){
if(dd > K)
return;
tti.push_back(mp(dd, ln));
for(auto x : T[u]){
if(x.fi == par)
continue;
dfs2(x.fi, u, cent, dd + x.se, ln + 1);
}
}
map<int, int> has;
int cnt = 0;
void split(int node){
++ cnt;
dfs1(node, -1);
int atl = subt[node] / 2;
int par = -1;
bool ok = true;
while(ok){
ok = false;
for(auto x : T[node]){
if(x.fi == par || use[x.fi])
continue;
if(subt[x.fi] > atl){
par = node;
node = x.fi;
ok = true;
break;
}
}
}
has.clear();
has[0] = 0;
for(auto x : T[node]){
if(!use[x.fi]){
tti.clear();
dfs2(x.fi, node, node, x.se, 1);
for(auto p : tti){
if(has.count(K-p.fi)){
if(res == -1 || res > p.se + has[K - p.fi])
res = p.se + has[K - p.fi];
}
}
for(auto p : tti){
if(!has.count(p.fi))
has[p.fi] = p.se;
else
has[p.fi] = min(has[p.fi], p.se);
}
}
}
use[node] = true;
for(auto x : T[node]){
if(use[x.fi])
continue;
split(x.fi);
}
}
int best_path(int n, int k, int h[][2], int ln[]){
K = k;
for(int i = 0 ; i < n-1; i ++ ){
T[h[i][0]].push_back(mp(h[i][1], ln[i]));
T[h[i][1]].push_back(mp(h[i][0], ln[i]));
}
split(0);
return res;
}
