#include <iostream>
#include <vector>
#include "race.h"
using namespace std;
const int N = 1e6 + 5, M = 1e6 + 5;
int t, n, m, k, a[N], sz[N], tmp[N], mx, l[N], r[N];
vector<pair<int, int>> v[N];
bool vis[N];
int ans = 1e9;
int get_subtree_sizes(int node, int p = -1) {
sz[node] = 1;
for (auto x:v[node]) if (x.first != p && !vis[x.first]) sz[node] += get_subtree_sizes(x.first, node);
return sz[node];
}
int get_centroid(int node, int size, int p = -1) {
for (auto x:v[node]) {
if (x.first == p || vis[x.first]) continue;
if (sz[x.first] >= size) return get_centroid(x.first, size, node);
}
return node;
}
void get_cnt(int node, int p, int yes, int sum, int level) {
if (sum > k) return;
if (sum == k) ans = min(ans, level);
if (yes == 1) tmp[sum] = min(tmp[sum], level);
else if (yes) tmp[sum] = 1e9;
else ans = min(ans, level + tmp[k - sum]);
for (auto x:v[node]) if (x.first != p && !vis[x.first]) get_cnt(x.first, node, yes, sum + x.second, level + 1);
}
void centroid_decomp(int node = 0) {
get_subtree_sizes(node);
int c = get_centroid(node, sz[node] / 2);
vis[c] = 1;
mx = 0;
for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 0, x.second, 1), get_cnt(x.first, c, 1, x.second, 1);
for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 2, x.second, 1);
for (auto x:v[c]) if (!vis[x.first]) centroid_decomp(x.first);
}
int best_path(int N, int K, int H[][2], int L[]) {
fill(tmp, tmp + 1000000 + 5, 1e9);
n = N, k = K;
for (int i = 1; i < n; i++) {
v[H[i][1]].push_back({H[i][0], L[i]});
v[H[i][0]].push_back({H[i][1], L[i]});
}
centroid_decomp();
return (ans == 1e9 ? -1 : ans);
}
