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