#include "race.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
const int N_NOEUDS = 1e6;
struct SousArbre {
map<int, int> profMin;
};
vector<SousArbre> arbre;
bool vu[N_NOEUDS];
int prof[N_NOEUDS], distRacine[N_NOEUDS];
vector<pii> voisins[N_NOEUDS];
int ans = N_NOEUDS, k;
int fusion(int pere, int fils, int noeud){
if (sz(arbre[pere].profMin) < sz(arbre[fils].profMin))
return fusion(fils, pere, noeud);
for (pii couple : arbre[fils].profMin){
int cible = k + 2 * distRacine[noeud] - couple.first;
if (arbre[pere].profMin.count(cible) == 1)
chmin(ans, couple.second + arbre[pere].profMin[cible] - 2 * prof[noeud]);
}
for (pii couple : arbre[fils].profMin){
if (arbre[pere].profMin.count(couple.first) == 1)
chmin(arbre[pere].profMin[couple.first], couple.second);
else
arbre[pere].profMin[couple.first] = couple.second;
}
return pere;
}
int parcours(int noeud, int etage, int dRoot){
vu[noeud] = true;
prof[noeud] = etage;
distRacine[noeud] = dRoot;
int ind = sz(arbre);
map<int, int> p; p[distRacine[noeud]] = prof[noeud];
arbre.pb({p});
for (pii sortant : voisins[noeud]){
int enfant = sortant.first, distSup = sortant.second;
if (vu[enfant]) continue;
ind = fusion(ind, parcours(enfant, etage + 1, dRoot + distSup), noeud);
}
return ind;
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
for (int ind = 0; ind < N - 1; ++ind){
int poids = L[ind], noeud = H[ind][0], voisin = H[ind][1];
voisins[noeud].pb({voisin, poids});
voisins[voisin].pb({noeud, poids});
}
int racine = parcours(0, 0, 0);
/*for (pii couple : arbre[racine].profMin)
cout << "paire " << couple.first << " " << couple.second << endl;*/
if (ans == N_NOEUDS) ans = -1;
return ans;
}
