#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define INF 999999999
int calcula_tam_subarvores(int nodo, int pai, vector<set<int>> &adj, vector<int> &sub){
sub[nodo] = 1;
for(int filho : adj[nodo]){
if(filho!=pai) sub[nodo] += calcula_tam_subarvores(filho, nodo, adj, sub);
}
return sub[nodo];
}
int acha_centroide(int nodo, int pai, int n, vector<set<int>> &adj, vector<int> &sub){
for(int filho : adj[nodo]){
if(filho!=pai && sub[filho]>n/2) return acha_centroide(filho, nodo, n, adj, sub);
}
return nodo;
}
unordered_map<int, unordered_map<int,int>> costs;
int ans = INF;
int get_cost(int u, int v){
auto it = costs.find(u);
if(it == costs.end()) return 0;
auto it2 = it->second.find(v);
if(it2 == it->second.end()) return 0;
return it2->second;
}
void dfs1(int start_node, int parent_node, vector<set<int>> &adj, unordered_map<int, int> &melhor,
vector<pair<int, int>> &memoria, int flag, int k, vector<int> &used_indices){
stack<tuple<int, int, int, int>> st; //nodo, pai, distancia e peso
int initial_weight = get_cost(parent_node, start_node);
st.push(make_tuple(start_node, parent_node, 1, initial_weight)); //coloca determinado filho do centroide na pilha
while(!st.empty()){
int node, pai, distancia_da_raiz, peso_ate_araiz;
tie(node, pai, distancia_da_raiz, peso_ate_araiz) = st.top(); st.pop();
if (peso_ate_araiz < 0 || peso_ate_araiz >= memoria.size()) {
continue;
}
//precisamos ver se existe caminho de custo k-peso_ate_araiz que termina na raiz atual
int weight_needed = k-peso_ate_araiz;
if(weight_needed>=0){ //nao negativo
auto aux = melhor.find((weight_needed));
if(aux!=melhor.end()){
ans = min(ans, aux->second+distancia_da_raiz);
}
}
//salva os caminhos que comecam na raiz e terminam em vertices dessa subarvore
if(memoria[peso_ate_araiz].second==flag){
memoria[peso_ate_araiz].first = min(memoria[peso_ate_araiz].first, distancia_da_raiz);
}else{ //primeira vez que este peso aparece para este flag
memoria[peso_ate_araiz] = {distancia_da_raiz, flag};
used_indices.push_back(peso_ate_araiz);
}
//agora colocar os filhos na pilha
for(int filho:adj[node]){
if(filho != pai){
st.push(make_tuple(filho, node, distancia_da_raiz+1, peso_ate_araiz+get_cost(node, filho)));
}
}
}
}
void resolve(vector<set<int>> &adj, int nodo, vector<pair<int, int>> &memoria, int k){
vector<int> sub(adj.size(), 0);
calcula_tam_subarvores(nodo, -1, adj, sub);
int centroid = acha_centroide(nodo, -1, sub[nodo], adj, sub);
unordered_map<int, int> melhor;
melhor[0] = 0; //so fica no centroid e nao anda
int flag = 1;
for(int filho:adj[centroid]){
vector<int> used_indices; //armazena apenas pesos usados por este filho
used_indices.reserve(256); //funciona?
dfs1(filho, centroid, adj, melhor, memoria, flag, k, used_indices);
//itera so sobre os indices usados
for(int w : used_indices){
if(memoria[w].second == flag){ //se eh atual
int dist = memoria[w].first; //distancia ate a raiz
if(!melhor.count(w)){ //se nao tiver um melhor daquele peso
melhor[w] = dist; //agora tem
}else{
melhor[w] = min(melhor[w], dist); //se tiver verifica se encontrou algum menos pesado
}
}
}
for(int w : used_indices){
memoria[w].first = 0;
memoria[w].second = 0;
}
flag++;
}
vector<int> filhos(adj[centroid].begin(), adj[centroid].end());
for(int filho : filhos) {
adj[centroid].erase(filho);
adj[filho].erase(centroid);
}
for(int filho : filhos){
resolve(adj, filho, memoria, k);
}
return;
}
int best_path(int N, int K, int H[][2], int L[]) {
ans = INF;
costs.clear();
vector<set<int>> adj(N);
for (int i = 0; i < N - 1; i++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
adj[u].insert(v);
adj[v].insert(u);
costs[u][v] = w;
costs[v][u] = w;
}
vector<pair<int, int>> memoria(1000000+10, {0, 0});
resolve(adj, 0, memoria, K);
if(ans == INF){
return -1;
}else{
return ans;
}
}
