#include <bits/stdc++.h>
#include "race.h"
using namespace std;
vector<pair<int, int> > g[20101];
int sz[20101];
bool del[20101];
void rcn(int v, int pred) {
sz[v] = 1;
for (auto [to, c] : g[v]) {
if (to == pred || del[to]) continue;
rcn(to, v);
sz[v] += sz[to];
}
}
int centroid(int v, int pred, int N) {
for (auto [to, c] : g[v]) {
if (to == pred || del[to])continue;
if (sz[to] > N / 2)
return centroid(to, v, N);
}
return v;
}
int Kur;
int have[20101];
int res = 1010101010;
void dfs(int v, int pred, int sum, int depth) {
if (sum > Kur)return;
if (have[Kur - sum] != -1)
res = min(res, have[Kur - sum] + depth);
for (auto [to, c] : g[v]) {
if (to == pred || del[to])continue;
dfs(to, v, sum + c, depth + 1);
}
}
void put(int v, int pred, int sum, int depth) {
if (sum > Kur)return;
if (have[sum] != -1)
have[sum] = min(have[sum], depth);
else
have[sum] = depth;
for (auto [to, c] : g[v]) {
if (to == pred || del[to])continue;
dfs(to, v, sum + c, depth + 1);
}
}
void decomposition(int v) {
del[v] = true;
rcn(v, v);
for (auto [to, c] : g[v]) {
if (del[to])continue;
dfs(to, v, c, 1);
put(to, v, c, 1);
}
for (auto [to, c] : g[v]) {
if (del[to])continue;
memset(have, -1, sizeof(have));
have[0] = 0;
decomposition(centroid(to, v, sz[to]));
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; i++) {
g[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
g[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
}
memset(have, -1, sizeof(have));
have[0] = 0;
Kur = K;
rcn(1, 1);
decomposition(centroid(1, 1, N));
// cout << centroid(1, 1, N) << " !!" << endl;
if (res == 1010101010)return -1;
return res;
}
/**
3 3
0 1 1
1 2 1
-1
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/
