#include "race.h"
#include <vector>
#include <iostream>
#include <map>
using namespace std;
int INFINI = 1000 * 1000 * 1000;
int nbVilles, tailleTotale;
vector<pair<int, int>> voisins[200 * 1000];
struct Retour {
long long decProf;
int decChemin;
map<long long, int> profs;
Retour() {
decChemin = 0;
decProf = 0;
profs[0] = 0;
}
void shift(long long taille) {
decChemin++;
decProf += taille;
}
int getChemin(long long prof) {
if(profs.find(prof - decProf) == profs.end())
return INFINI;
return profs[prof - decProf] + decChemin;
}
void setChemin(long long prof, int chemin) {
profs[prof - decProf] = chemin - decChemin;
}
vector<pair<long long, int>> getProfs() {
vector<pair<long long, int>> res;
for(pair<long long, int> paire : profs) {
res.push_back({paire.first + decProf, paire.second + decChemin});
}
return res;
}
};
vector<Retour> retours;
int melChemin = INFINI;
int fusion(int a, int b) {
Retour& retA = retours[a];
Retour& retB = retours[b];
if(retA.profs.size() > retB.profs.size()) {
return fusion(b, a);
}
vector<pair<long long, int>> profsA = retA.getProfs();
for(pair<long long, int> paire : profsA) {
melChemin = min(melChemin, paire.second + retB.getChemin(tailleTotale - paire.first));
}
for(pair<long long, int> paire : profsA) {
retB.setChemin(paire.first, min(retB.getChemin(paire.first), paire.second));
}
return b;
}
int calcChemin(int noeud, int parent = -1) {
int id = retours.size();
retours.push_back(Retour());
for(pair<int, int> voisin : voisins[noeud]) {
if(voisin.first == parent)
continue;
int retour = calcChemin(voisin.first, noeud);
retours[retour].shift(voisin.second);
id = fusion(id, retour);
}
return id;
}
int best_path(int _nbVilles, int _tailleTotale, int adjs[][2], int tailles[]) {
nbVilles = _nbVilles;
tailleTotale = _tailleTotale;
for(int iRoute = 0;iRoute < nbVilles - 1;iRoute++) {
voisins[adjs[iRoute][0]].push_back({adjs[iRoute][1], tailles[iRoute]});
voisins[adjs[iRoute][1]].push_back({adjs[iRoute][0], tailles[iRoute]});
}
calcChemin(0);
if(melChemin == INFINI)
return -1;
return melChemin;
}
