#include <cstdio>
#include <iostream>
#include <vector>
#include "race.h"
using namespace std;
const int INFINI = (1000 * 1000 * 1000);
const int MAX_NOEUDS = (200 * 1000);
const int DIST_MAX = (1000 * 1000);
vector <pair <int, int>> Voisins[MAX_NOEUDS];
pair <pair <int, int>, pair <int, int>> DistancesMin[DIST_MAX];
vector <int> Update;
bool Traite[MAX_NOEUDS];
int NbFils[MAX_NOEUDS];
int cible;
void Init() {
for (int i = 0; i < DIST_MAX; i ++)
{
DistancesMin[i].first = DistancesMin[i].second = {INFINI, -1};
}
return;
}
int Count(int noeud, int pere) {
int sum = 1;
for (pair <int, int> dest : Voisins[noeud])
{
if (!Traite[dest.first] && dest.first != pere)
sum += Count(dest.first, noeud);
}
return NbFils[noeud] = sum;
}
int FindCentroide(int noeud, int pere, int borne) {
for (pair <int, int> dest : Voisins[noeud])
{
if (!Traite[dest.first] && dest.first != pere && NbFils[dest.first] > borne)
return FindCentroide(dest.first, noeud, borne);
}
return noeud;
}
void Explore(int noeud, int pere, int dist, int prof, int compo) {
if (dist > cible)
return;
Update.push_back(dist);
if (prof < DistancesMin[dist].first.first)
{
if (compo != DistancesMin[dist].first.second)
DistancesMin[dist].second = DistancesMin[dist].first;
DistancesMin[dist].first = {prof, compo};
}
else if (prof < DistancesMin[dist].second.first && compo != DistancesMin[dist].first.second)
DistancesMin[dist].second = {prof, compo};
for (pair <int, int> dest : Voisins[noeud])
{
if (!Traite[dest.first] && dest.first != pere)
Explore(dest.first, noeud, dist + dest.second, prof + 1, compo);
}
return;
}
int TraiteCentroide(int noeud) {
int nb = 0;
DistancesMin[0].first = {0, -1};
for (pair <int, int> dest : Voisins[noeud])
{
if (!Traite[dest.first])
{
Explore(dest.first, noeud, dest.second, 1, nb ++);
}
}
int ans = INFINI;
for (int a : Update)
{
if (DistancesMin[a].first.second != DistancesMin[cible - a].first.second)
ans = min(ans, DistancesMin[a].first.first + DistancesMin[cible - a].first.first);
else
{
ans = min(ans, DistancesMin[a].first.first + DistancesMin[cible - a].second.first);
ans = min(ans, DistancesMin[a].second.first + DistancesMin[cible - a].first.first);
}
}
for (int a : Update)
{
DistancesMin[a].first = DistancesMin[a].second = {INFINI, -1};
}
Update.clear();
Traite[noeud] = true;
for (pair <int, int> dest : Voisins[noeud])
{
if (!Traite[dest.first])
{
Count(dest.first, noeud);
ans = min(ans, TraiteCentroide(FindCentroide(dest.first, noeud, NbFils[dest.first] / 2)));
}
}
return ans;
}
int best_path(int nbSommets, int target, int Aretes[][2], int Poids[]) {
for (int i = 0; i < nbSommets - 1; i ++)
{
Voisins[Aretes[i][0]].push_back({Aretes[i][1], Poids[i]});
Voisins[Aretes[i][1]].push_back({Aretes[i][0], Poids[i]});
}
cible = target;
Init();
Count(0, -1);
int r = TraiteCentroide(FindCentroide(0, -1, NbFils[0] / 2));
if (r == INFINI)
r = -1;
return r;
}
