#include <iostream>
#include <vector>
#include <algorithm>
#include <map> // Usar map ao invés de unordered_map pode ser mais estável em alguns casos.
#include "race.h"
using namespace std;
const int INF = 1e9; // Um infinito maior é mais seguro
int N_global;
long long K_global;
vector<vector<pair<int, int>>> adj; // {vizinho, peso}
vector<int> subtree_size;
vector<bool> is_removed;
int min_edges = INF;
// Calcula o tamanho das subárvores
void get_subtree_sizes(int u, int p) {
subtree_size[u] = 1;
for (auto& edge : adj[u]) {
int v = edge.first;
if (v != p && !is_removed[v]) {
get_subtree_sizes(v, u);
subtree_size[u] += subtree_size[v];
}
}
}
// Encontra o centroide da árvore/subárvore atual
int get_centroid(int u, int p, int total_size) {
for (auto& edge : adj[u]) {
int v = edge.first;
if (v != p && !is_removed[v] && subtree_size[v] * 2 > total_size) {
return get_centroid(v, u, total_size);
}
}
return u;
}
// DFS para encontrar todos os caminhos a partir do centroide
// Armazena os pares {comprimento, num_arestas}
void dfs_paths(int u, int p, long long current_len, int current_edges, vector<pair<long long, int>>& paths) {
if (current_len > K_global) {
return;
}
paths.push_back({current_len, current_edges});
for (auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
if (v != p && !is_removed[v]) {
dfs_paths(v, u, current_len + weight, current_edges + 1, paths);
}
}
}
// Função principal da Decomposição por Centroide
void decompose(int entry_node) {
get_subtree_sizes(entry_node, -1);
int centroid = get_centroid(entry_node, -1, subtree_size[entry_node]);
// Mapa para armazenar os melhores caminhos (comprimento -> min_arestas)
// que começam no centroide atual.
map<long long, int> best_paths;
best_paths[0] = 0; // Caminho de comprimento 0 tem 0 arestas
for (auto& edge : adj[centroid]) {
int neighbor = edge.first;
if (!is_removed[neighbor]) {
vector<pair<long long, int>> paths_from_neighbor;
// Coleta todos os caminhos na subárvore do vizinho
dfs_paths(neighbor, centroid, edge.second, 1, paths_from_neighbor);
// Para cada caminho encontrado, tenta achar um par no mapa 'best_paths'
for (const auto& path : paths_from_neighbor) {
long long len = path.first;
int edges = path.second;
if (K_global >= len) {
long long needed = K_global - len;
if (best_paths.count(needed)) {
min_edges = min(min_edges, edges + best_paths[needed]);
}
}
}
// Adiciona os caminhos coletados ao mapa 'best_paths' para as próximas subárvores
for (const auto& path : paths_from_neighbor) {
long long len = path.first;
int edges = path.second;
if (!best_paths.count(len) || edges < best_paths[len]) {
best_paths[len] = edges;
}
}
}
}
is_removed[centroid] = true;
// Chama recursivamente para as subárvores restantes
for (auto& edge : adj[centroid]) {
int v = edge.first;
if (!is_removed[v]) {
decompose(v);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
// Reset de variáveis globais para múltiplos casos de teste (se houver)
min_edges = INF;
N_global = N;
K_global = K;
adj.assign(N, vector<pair<int, int>>());
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({v, w});
adj[v].push_back({u, w});
}
subtree_size.assign(N, 0);
is_removed.assign(N, false);
decompose(0);
return (min_edges == INF) ? -1 : min_edges;
}
