#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define INF LLONG_MAX/2
int flagAtual=1;
vector<pair<int, ll>> melhor;
vector<bool> block;
// Respota.
ll menor_K = INF;
// Isso ajuda na memoria da recursão???
vector<vector<pair<int, ll>>> adj;
vector<int> subtreeSz;
//calcula o tamanho da subarvore
void get_SubTreeSize(int v, int pai) {
subtreeSz[v] = 1;
for(auto& [u, val] : adj[v]) {
if(u == pai || block[u]) continue;
get_SubTreeSize(u,v);
subtreeSz[v] += subtreeSz[u];
}
}
//percorre todos os vertices e retorna o centroide...
int findCentroid(int v, int pai, int size) {
int mais_verts=-1; int next=-1;
bool isCentroid = true;
for (auto &[ch, val] : adj[v])
if (ch != pai && !block[ch]) {
if (subtreeSz[ch] > mais_verts) {
mais_verts = subtreeSz[ch];
next = ch;
}
if (2 * subtreeSz[ch] > size)
isCentroid = false;
}
if (!isCentroid) {
subtreeSz[v] = size + 1 - subtreeSz[v];
return findCentroid(next, v, size);
}
return v;
}
// DFS 1:
// Percorrer sua subárvore, vendo se tem algum caminho terminando em cada vértice
// (exemplo: no vert 7, com peso 5 e tam 2 → tem algum caminho terminando na raiz
// com peso 9?). Ver se caminho assim fica menor.
void dfs1(int v, int pai, ll dist, int total, int K) {
if(dist > K) return;
ll aux = melhor[K-dist].second == flagAtual? melhor[K-dist].first : INF;
if(aux + total < menor_K)
menor_K = aux + total;
for(auto& [ch, val] : adj[v])
if(ch != pai && !block[ch])
dfs1(ch, v, dist + val, total+1, K);
}
// DFS 2:
// Atualizar o array “melhor”, adicionando os caminhos dessa subárvore.
void dfs2(int v, int pai, ll dist, int total, int K) {
if(dist > K) return;
if(melhor[dist].first > total || melhor[dist].second < flagAtual) {
melhor[dist].first = total;
melhor[dist].second = flagAtual;
}
for (auto& [ch, val] : adj[v])
if(!block[ch] && ch != pai)
dfs2(ch, v, dist + val, total + 1, K);
}
int best_path(int N, int K, int H[][2], int L[]) {
adj = vector<vector<pair<int, ll>>>(N);
subtreeSz = vector<int>(N, 0);
melhor.assign(K+1, {INF, 0});
block.assign(N, false);
menor_K = INF;
flagAtual = 1;
for(int i = 0; i < N-1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
queue<int> Q;
int node;
Q.push(0);
while (!Q.empty()) {
node = Q.front();
get_SubTreeSize(node, -1);
node = findCentroid(node, -1, subtreeSz[node]);
block[node] = true;
melhor[0] = {0, flagAtual};
for (auto& [ch, val] : adj[node])
if (!block[ch]) {
dfs1(ch, node, val, 1, K);
dfs2(ch, node, val, 1, K);
Q.push(ch);
}
Q.pop();
flagAtual++;
}
if(menor_K == INF) menor_K = -1;
return menor_K;
}
