#include "race.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define nmax 200008
#define kmax 1000008
const int inf = 1e9;
using namespace std;
typedef pair<int, int> pii;
int n, k, lim, ans = inf, sz[nmax], f[kmax];
bool kt[nmax];
vector<pii>l[nmax];
int dfs(int x, int pre){
sz[x] = 1;
for (pii it : l[x]){
if (it.fi == pre || kt[it.fi])
continue;
sz[x] += dfs(it.fi, x);
}
return sz[x];
}
int centroid(int rt, int x, int pre){
for (pii it : l[x]){
if (it.fi == pre || kt[it.fi])
continue;
if (sz[it.fi] * 2 > sz[rt])
return centroid(rt, it.fi, x);
}
return x;
}
void calc(int x, int pre, int dis, int d, int flag){
if (dis > k)
return;
switch(flag){
case 0:
ans = min(ans, f[k - dis] + d);
break;
case 1:
f[dis] = min(f[dis], d);
break;
default:
f[dis] = inf;
break;
}
for (pii it : l[x]){
if (it.fi == pre || kt[it.fi])
continue;
calc(it.fi, x, dis + it.se, d + 1, flag);
}
}
void centroid(int x){
dfs(x, x);
x = centroid(x, x, x);
f[0] = 0;
for (pii it : l[x])
if (!kt[it.fi]){
calc(it.fi, x, it.se, 1, 0);
calc(it.fi, x, it.se, 1, 1);
}
for (pii it : l[x])
if (!kt[it.fi])
calc(it.fi, x, it.se, 1, 2);
kt[x] = 1;
f[0] = -1;
for (pii it : l[x])
if (!kt[it.fi])
centroid(it.fi);
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
for (int i = 0; i < n - 1; i++){
int u = H[i][0], v = H[i][1], w = L[i];
l[u].push_back({v, w});
l[v].push_back({u, w});
}
memset(kt, false, sizeof(kt));
fill(f, f + n + 1, inf);
centroid(1);
if (ans >= n)
ans = -1;
return ans;
}
