#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define INF INT_MAX/2
int flagAtual=1;
vector<pair<int, int>> melhor;
vector<bool> block;
//calcula o tamanho da subarvore
void get_SubTreeSize( vector<vector<pair<int, int>>> &adj, vector<int> &subtreeSz, int v, int pai) {
subtreeSz[v] = 1;
for(auto& [u, val] : adj[v]) {
if(u == pai || block[u]) continue;
get_SubTreeSize(adj,subtreeSz,u,v);
subtreeSz[v] += subtreeSz[u];
}
}
//percorre todos os vertices e retorna o centroide...
int findCentroid(vector<vector<pair<int, int>>> &adj, vector<int> &subtreeSz, int v, int pai) {
for (auto &[chi, val] : adj[v])
if (chi != pai && !block[chi] && subtreeSz[chi] * 2 > adj.size())
return findCentroid(adj, subtreeSz, chi, v);
return v;
}
void dfs1(vector<vector<pair<int, int>>>&adj, int v, int pai, int dist, int total) {
if(dist >= melhor.size()) return;
melhor[dist].first = melhor[dist].second < flagAtual? total : min(total, melhor[dist].first);
melhor[dist].second = flagAtual;
for (auto& [ch, val] : adj[v])
if(!block[ch] && ch != pai) dfs1(adj, ch, v, dist + val, total+1);
}
void dfs2(vector<vector<pair<int, int>>>&adj, int v, int pai, int dist, int total, int K) {
if(dist >= melhor.size() || dist >= K) return;
if(melhor[K-dist].second == flagAtual) {
melhor[K].first = melhor[K].second < flagAtual? melhor[dist].first + melhor[K-dist].first : min(melhor[dist].first + melhor[K-dist].first, melhor[K].first);
melhor[K].second = flagAtual;
}
for (auto& [ch, val] : adj[v])
if(!block[ch] && ch != pai) dfs2(adj, ch, v, dist + val, total+1, K);
}
int best_path(int N, int K, int H[][2], int L[]) {
vector<vector<pair<int, int>>> adj(N); vector<int> subtreeSz(N);
melhor.resize(1000001, {INF, 0});
block.resize(N, false);
int menor_K = INF;
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]});
}
get_SubTreeSize(adj, subtreeSz, 0, -1);
queue<int> Q;
Q.push(findCentroid(adj, subtreeSz, 0, -1));
while(!Q.empty()) {
int node = Q.front();
Q.pop();
dfs1(adj, node, -1, 0, 0);
dfs2(adj, node, -1, 0, 0, K);
menor_K = melhor[K].second < flagAtual? menor_K : min(menor_K, melhor[K].first);
get_SubTreeSize(adj, subtreeSz, node, -1);
for(auto& [ch, val] : adj[node])
if(!block[ch]) Q.push(findCentroid(adj, subtreeSz, ch, node));
flagAtual++;
block[node] = true;
}
if(menor_K == INF) return -1;
return menor_K;
}
