#include "race.h"
#include <vector>
#include <algorithm>
const int MAX_N = 200'000;
const int MAX_K = 1'000'000;
struct Edge {
int v, w;
};
int n, k;
std::vector<Edge> adj[MAX_N];
bool dead[MAX_N];
int sz[MAX_N];
int size;
int min_edges[MAX_K + 1];
int min_nodes;
void size_dfs(int u, int prev = -1) {
sz[u] = 1;
for(auto &[v, w] : adj[u]) {
if(v != prev && !dead[v]) {
size_dfs(v, u);
sz[u] += sz[v];
}
}
}
int find_centroid(int u, int prev = -1) {
for(auto &[v, w] : adj[u]) {
if(v != prev && !dead[v] && sz[v] > size / 2) {
return find_centroid(v, u);
}
}
return u;
}
void update_result(int u, int sum_w, int depth, int prev = -1) {
if(sum_w > k) return;
int rem = k - sum_w;
if(min_edges[rem] + depth < min_nodes) {
min_nodes = min_edges[rem] + depth;
}
for(auto &[v, w] : adj[u]) {
if(v != prev && !dead[v]) {
update_result(v, sum_w + w, depth + 1, u);
}
}
}
void update_min_edges(int u, int sum_w, int depth, int prev = -1) {
if(sum_w > k) return;
min_edges[sum_w] = std::min(min_edges[sum_w], depth);
for(auto &[v, w] : adj[u]) {
if(v != prev && !dead[v]) {
update_min_edges(v, sum_w + w, depth + 1, u);
}
}
}
void reset(int u, int sum_w, int prev = -1) {
if(sum_w > k) return;
min_edges[sum_w] = 1e9;
for(auto &[v, w] : adj[u]) {
if(v != prev && !dead[v]) {
reset(v, sum_w + w, u);
}
}
}
void centroid_decomp(int root) {
size_dfs(root);
size = sz[root];
int centroid = find_centroid(root);
dead[centroid] = true;
min_edges[0] = 0;
for(auto &[v, w] : adj[centroid]) {
if(v != centroid && !dead[v]) {
update_result(v, w, 1);
update_min_edges(v, w, 1);
}
}
for(auto &[v, w] : adj[centroid]) {
if(v != centroid && !dead[v]) {
reset(v, w);
}
}
for(auto &[v, w]: adj[centroid]) {
if(v != centroid && !dead[v]) {
centroid_decomp(v);
}
}
}
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];
int v = H[i][1];
int w = L[i];
adj[u].push_back(Edge { v, w });
adj[v].push_back(Edge { u, w });
}
for(int i = 1; i <= k; i++) {
min_edges[i] = 1e9;
}
min_nodes = 1e9;
centroid_decomp(0);
return min_nodes == 1e9 ? -1 : min_nodes;
}
