#include "race.h"
#include <bits/stdc++.h>
using namespace std;
//calcula o tamanho da subarvore
void dfs( vector<vector< pair<int,int> > > &adj, vector<int> &subtreeSz, vector<bool> &bloqueados, int v, int pai) {
int tam = 1; //tamanho = 1 + tam dos filhos
for(auto &[w,peso]:adj[v]) if(w!=pai && !bloqueados[w]) {
dfs(adj,subtreeSz,bloqueados, w,v);
tam += subtreeSz[w];
}
subtreeSz[v] = tam;
}
//vetor que pode ser "zerado" para INT_MAX em O(1)
class VetorZeravelO1 {
private:
int flagAtual;
vector<int> melhorCaminho;
vector<int> flagElementos; //flag usada em cada elemento
public:
VetorZeravelO1(int n): flagAtual(1), melhorCaminho(n), flagElementos(n,0) {}
//ao trocar a flag, todos valores ficam "zerados" (infinitos), pois usavam a flag antiga
void zeraTodosValores() {
flagAtual++;
}
void set(int pos, int caminho) {
if(ehInfinito(pos)) { //eh infinito!
flagElementos[pos] = flagAtual;
melhorCaminho[pos] = caminho;
}
melhorCaminho[pos] =caminho;
}
int get(int pos) {
if(ehInfinito(pos)) return INT_MAX;
else return melhorCaminho[pos];
}
bool ehInfinito(int pos) {
return (flagElementos[pos]!=flagAtual); //se a flag for igual --> esta inicializado. Se nao for --> nao esta inicializado (eh infinito)
}
int size() {
return melhorCaminho.size();
}
};
int melhorResposta = INT_MAX;
//percorre todos os vertices e retorna o centroide...
//como os componentes vao mudando de tamanho (a medida em que vertices sao bloqueados), temos que passar isso...
int findCentroid( vector<vector< pair<int,int> > > &adj, vector<int> &subtreeSz, vector<bool> &bloqueados, int numVertComponente, int v, int pai) {
//se todas subarvores geradas ao remover v ficam com tamanho <= n/2 --> v eh centroide..
bool ehCentroide = true;
int tamCima = numVertComponente - subtreeSz[v]; //tamanho da parte de "cima da arvore" (cc do pai de v, se v for removido)
if(tamCima > numVertComponente/2) ehCentroide = false;
for(auto &[w,peso]:adj[v]) if(w!=pai && !bloqueados[w]) { //confere os filhos
if(subtreeSz[w] > numVertComponente/2) { ehCentroide = false; break; }
}
if(ehCentroide) return v;
//se nao for v, entao eh um dos filhos...
for(auto &[w,peso]:adj[v]) if(w!=pai && !bloqueados[w]) {
int ans = findCentroid(adj,subtreeSz,bloqueados,numVertComponente, w,v);
if(ans!=-1) return ans;
}
return -1; //nao achou nesta subarvore...
}
//melhor caminho que termina no vertice v, tendo distancia total k
//calcula para cada distancia possivel
//peso parcial tem o peso parcial da raiz ate v, tamParcial tem o mesmo para o tamanho
int melhorTerminando(int v, int pai, vector<vector< pair<int,int> > > &adj, vector<bool> &bloqueados,
VetorZeravelO1 &melhor, int k, int pesoParcial, int tamParcial) {
if(bloqueados[v]) return INT_MAX;
if(pesoParcial > k) return INT_MAX; //ultrapassei o peso! nao tem jeito... para evitar TLE
if(tamParcial>=melhorResposta) return INT_MAX; //nao vai ajudar em nada!
int mi= INT_MAX;
//qual o melhor caminho que passa na raiz e termina exatamente no vertice atual?
//ele tem tamanho melhor[k - pesoParcial] do filho anterior ate a raiz + tamParcial da raiz ate v
if(melhor.get(k - pesoParcial) != INT_MAX)
mi = min( mi , melhor.get(k - pesoParcial) + tamParcial );
//qual o melhor que termina em algum dos filhos (ou mais para baixo)?
for(auto &[w,peso]: adj[v]) if(w!=pai && !bloqueados[w]) {
mi = min(mi, melhorTerminando(w,v, adj,bloqueados, melhor, k, pesoParcial + peso, tamParcial+1));
}
return mi;
}
//calcula o melhor de cada peso que vai de v ateh a raiz
void calculaMelhorTerminandoRaiz(int v, int pai, vector<vector< pair<int,int> > > &adj, vector<bool> &bloqueados,
VetorZeravelO1 &melhor, int k, int pesoParcial, int tamParcial) {
if(bloqueados[v]) return;
if(pesoParcial > k) return; //para evitar TLE...
if(tamParcial>=melhorResposta) return; //nao vai ajudar em nada!
//qual o melhor caminho que passa na raiz e termina exatamente no vertice atual?
if(pesoParcial >= melhor.size()) return; //atencao aqui! O peso parcial pode crescer e ficar bem maior que o K maximo, dando RE (tecnicamente eu poderia parar ao ultrapassar...)
melhor.set(pesoParcial , min( tamParcial , melhor.get(pesoParcial) ) );
//qual o melhor que termina em algum dos filhos (ou mais para baixo)?
for(auto &[w,peso]: adj[v]) if(w!=pai && !bloqueados[w]) {
calculaMelhorTerminandoRaiz(w,v, adj,bloqueados, melhor, k, pesoParcial + peso, tamParcial+1);
}
}
int dAnt = -1;
//Encontra o melhor caminho de peso k no CC de v, considerando que os vertices "testados" estao bloqueados (ou seja, eles dividem a arvore em varios CCs)
void encontraMelhorCaminho(VetorZeravelO1 &melhor, vector<vector< pair<int,int> > > &adj, vector<int> &subtreeSz,
vector<bool> &bloqueados, int numVertComponente, int k, int v, int d=0) {
//int mi= INT_MAX;
//cerr << endl << endl;
//cerr << "V = " << v << " tam " << numVertComponente << endl;
//ou o caminho com o minimo de arestas passa pela raiz ou nao.
//vamos escolher o centroide como nova raiz da arvore atual...
dfs(adj,subtreeSz,bloqueados,v,-1); //calcula o tamanho das subarvores, escolhendo v como raiz
int centroide = findCentroid(adj, subtreeSz, bloqueados, subtreeSz[v], v, -1);
//cerr << "Calculando com centroide " << centroide << endl;
melhor.zeraTodosValores(); //colocar infinito em todo vetor de melhores.
//iniciar o melhor[0] ?
melhor.set(0, 0);
//encontre o melhor caminho que passa pelo centroide...
for(auto &[w,peso]:adj[centroide]) if(!bloqueados[w]) {
//para cada filho w, vamos calcular o menor caminho de distancia 0, de distancia 1, de distancia 2, ....
//e que termina em v (logo apos passar por w)
//ANTES DISSO, eu atualizo o melhor que comeca no componente de um filho ja processado e termina no do filho atual
// melhor[i] jah tem o melhor caminho de comprimento i que passa em um filho anterior e termina em v
int melhorComecaFilhoTerminaW = melhorTerminando(w, centroide, adj, bloqueados, melhor,k, peso, 1);
//mi = min( mi, melhorComecaFilhoTerminaW);
melhorResposta = min(melhorResposta, melhorComecaFilhoTerminaW);
//cout << "Melhor termina w " << w << " " << melhorComecaFilhoTerminaW << endl;
//agora, fazemos uma DFS para incluir no contador "melhor" os melhores de cada tamanho que terminam em v...
calculaMelhorTerminandoRaiz(w, centroide, adj, bloqueados,melhor,k, peso,1);
/*cout << "Apos filho w " << w << endl;
for(int i=0;i<100000;i++) if(melhor[i]!=INT_MAX) cout << i << " " << melhor[i] << endl;
cout << endl;*/
}
//considerar melhor que comeca em um filho e termina na raiz, tendo peso exatamente k
// mi = min(mi, melhor.get(k));
melhorResposta = min(melhor.get(k), melhorResposta);
//encontre o melhor caminho estao completamente nas subarvores dos filhos, nao passando por esse centroide
bloqueados[centroide] = true; //bloqueia, dividindo a arvore em mais CCs
for(auto &[w,peso]:adj[centroide]) if(!bloqueados[w]) {
encontraMelhorCaminho(melhor,adj,subtreeSz,bloqueados,subtreeSz[w],k,w,d+1);
}
}
int best_path(int n, int k, int H[][2], int L[]) {
vector<vector< pair<int,int> > > adj(n);
for(int i=0;i<n-1;i++) {
int a = H[i][0];
int b = H[i][1];
int w = L[i];
adj[a].push_back(make_pair(b,w ) );
adj[b].push_back(make_pair(a,w ) );
}
VetorZeravelO1 melhor(k+2); //Vai dar TLE se ficar recriando sempre... usar auxiliar para marcar se esta preenchido ou nao
vector<int> subtreeSz(n);
vector<bool> bloqueados(n,false);
dfs(adj,subtreeSz,bloqueados,0,-1); //calcula o tamanho das subarvores, escolhendo 0 (arbitrariamente) como raiz
encontraMelhorCaminho(melhor,adj,subtreeSz,bloqueados,n,k,0);
if(melhorResposta==INT_MAX) melhorResposta = -1;
return melhorResposta;
/*int mi= INT_MAX;
for(int i=0;i<n;i++) {
vector<int> visit(n,false);
int ans = melhor(i,adj,visit,k);
mi = min(mi, ans);
}
if(mi==INT_MAX) mi = -1;
return mi;*/
}
