#include "race.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define mk make_pair
#define pb push_back
#define sc second
#define fr first
#define pii pair < int, int >
#define vii vector < pii >
const int MAXN = 2e5 + 7;
const int MAXK = 1e6 + 7;
const int INF = 1e9 + 7;
int ans = INF, k, t;
int st[MAXK], mt[MAXK], h[MAXN], del[MAXN];
vii g[MAXN];
void dfs (int v, int p = -1){
h[v] = 1;
for (pii to : g[v])
if (to.fr != p && !del[to.fr])
dfs(to.fr, v);
if (p != -1)
h[p] += h[v];
}
int centroid (int v){
dfs(v);
bool ok = true;
int c = v, pr = 0;
while (ok){
ok = false;
for (pii to : g[c]){
if (to.fr != pr && !del[to.fr] && h[to.fr] * 2 >= h[v]){
pr = c;
c = to.fr;
ok = true;
break;
}
}
}
return c;
}
void findAns (int v, int p, int l, int d = 1){
if (k > l && mt[k - l] == t)
ans = min(ans, d + st[k - l]);
else if (k == l)
ans = min(ans, d);
if (l > k)
return;
for (pii to : g[v])
if (to.fr != p && !del[to.fr])
findAns (to.fr, v, l + to.sc, d + 1);
}
void upd (int v, int p, int l, int d = 1){
if (k > l && mt[l] != t){
mt[l] = t;
st[l] = d;
}
else if (k > l)
st[l] = min(d, st[l]);
else
return;
for (pii to : g[v])
if (to.fr != p && !del[to.fr])
upd(to.fr, v, l + to.sc, d + 1);
}
void calc (int v = 0){
v = centroid(v);
del[v] = 1;
t++;
for (pii to : g[v]){
if (!del[to.fr]){
findAns(to.fr, v, to.sc);
upd(to.fr, v, to.sc);
}
}
for (pii to : g[v])
if (!del[to.fr])
calc (to.fr);
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for (int i = 0; i < N - 1; i++){
g[H[i][0]].pb(mk(H[i][1], L[i]));
g[H[i][1]].pb(mk(H[i][0], L[i]));
}
calc();
if (ans == INF)
return -1;
return ans;
}
