#include "race.h"
#include <bits/stdc++.h>
using namespace std;
static vector < pair <int , int> > adiacenta[200000];
static int inceput[200000] , sfarsit[200000] , ordine[200001] , rezultat = INT32_MAX;
static pair <int , int64_t> adancime[200000];
static map <int64_t , int> candidati;
int Precalculare (const int nod , const int sursa)
{
ordine[++ordine[0]] = nod;
inceput[nod] = ordine[0];
int cantitate = 1 , maxim = 0;
for (int indice = 0 ; indice < (int)adiacenta[nod].size() ; indice++)
{
if (adiacenta[nod][indice].first == sursa)
{ swap(adiacenta[nod][indice] , adiacenta[nod].back()); adiacenta[nod].pop_back(); indice--; continue; }
adancime[adiacenta[nod][indice].first] = {adancime[nod].first + 1 , adancime[nod].second + adiacenta[nod][indice].second};
const int termen = Precalculare(adiacenta[nod][indice].first , nod);
if (termen > maxim)
{ swap(adiacenta[nod][indice] , adiacenta[nod][0]); maxim = termen; }
cantitate += termen;
}
sfarsit[nod] = ordine[0];
return cantitate;
}
void Solve (const int nod , const int dorit , const bool elimina)
{
for (int indice = 1 ; indice < (int)adiacenta[nod].size() ; indice++)
{ Solve(adiacenta[nod][indice].first , dorit , true); }
if (!adiacenta[nod].empty())
{ Solve(adiacenta[nod][0].first , dorit , false); }
auto locatie = candidati.find(adancime[nod].second + dorit);
if (locatie != candidati.end())
{ rezultat = min(rezultat , locatie -> second - adancime[nod].first); }
candidati[adancime[nod].second] = adancime[nod].first;
for (int indice = 1 ; indice < (int)adiacenta[nod].size() ; indice++)
{
int& vecin = adiacenta[nod][indice].first;
for (int __indice = inceput[vecin] ; __indice <= sfarsit[vecin] ; __indice++)
{
int& __nod = ordine[__indice];
const pair <int , int64_t> termen = {adancime[__nod].first - adancime[nod].first , adancime[__nod].second - adancime[nod].second};
locatie = candidati.find(dorit - termen.second + adancime[nod].second);
if (locatie != candidati.end())
{ rezultat = min(rezultat , termen.first + locatie -> second - adancime[nod].first); }
}
for (int __indice = inceput[vecin] ; __indice <= sfarsit[vecin] ; __indice++)
{
int& __nod = ordine[__indice];
locatie = candidati.find(adancime[__nod].second);
if (locatie != candidati.end())
{ locatie -> second = min(locatie -> second , adancime[__nod].first); }
else
{ candidati[adancime[__nod].second] = adancime[__nod].first; }
}
}
if (elimina)
{ candidati.clear(); }
}
int best_path (int numar_noduri , int dorit , int muchii[][2] , int cost[])
{
for (int indice = 0 ; indice < numar_noduri - 1 ; indice++)
{
adiacenta[muchii[indice][0]].emplace_back(muchii[indice][1] , cost[indice]);
adiacenta[muchii[indice][1]].emplace_back(muchii[indice][0] , cost[indice]);
}
Precalculare(0 , -1);
Solve(0 , dorit , false);
if (rezultat == INT32_MAX)
{ rezultat = -1; }
return rezultat;
}
