#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
pair <int , long long> adancime[500001];
vector < pair <int , int> > adiacenta[500001];
int cantitate[500001] , sursa[500001] , inceput[500001] , tabel[20][500001] , moment[500001];
bool vizitat[500001];
inline int Combina (const int nod_1 , const int nod_2)
{
return adancime[nod_1].first < adancime[nod_2].first ? nod_1 : nod_2;
}
inline int LCA (int nod_1 , int nod_2)
{
nod_1 = inceput[nod_1];
nod_2 = inceput[nod_2];
if (nod_1 > nod_2)
{ swap(nod_1 , nod_2); }
int exponent = 0;
while ((1 << (exponent + 1)) <= nod_2 - nod_1 + 1)
{ exponent++; }
return Combina(tabel[exponent][nod_1] , tabel[exponent][nod_2 - (1 << exponent) + 1]);
}
inline long long Distanta (int nod_1 , int nod_2)
{
return adancime[nod_1].second + adancime[nod_2].second - 2 * adancime[LCA(nod_1 , nod_2)].second;
}
inline void BuildRMQ (const int nod , const int __sursa)
{
tabel[0][++tabel[0][0]] = nod;
inceput[nod] = tabel[0][0];
for (auto& vecin : adiacenta[nod]) {
if (vecin.first != __sursa)
{
adancime[vecin.first] = {adancime[nod].first + 1 , adancime[nod].second + vecin.second};
BuildRMQ(vecin.first , nod);
tabel[0][++tabel[0][0]] = nod;
}
}
}
inline void Parcurgere (const int nod , const int __sursa)
{
cantitate[nod] = 1;
for (auto& vecin : adiacenta[nod]) {
if (!vizitat[vecin.first] && vecin.first != __sursa)
{
Parcurgere(vecin.first , nod);
cantitate[nod] += cantitate[vecin.first];
}
}
}
inline int GetCentroid (int nod)
{
Parcurgere(nod , 0);
while (true)
{
bool gasit = false;
for (auto& vecin : adiacenta[nod]) {
if (!vizitat[vecin.first] && cantitate[vecin.first] > cantitate[nod] / 2)
{
cantitate[nod] -= cantitate[vecin.first];
cantitate[vecin.first] += cantitate[nod];
nod = vecin.first;
gasit = true;
break;
}
}
if (gasit)
{ break; }
}
return nod;
}
inline void Build (int nod , const int anterior)
{
vizitat[nod] = true;
nod = GetCentroid(nod);
sursa[nod] = anterior;
for (auto& vecin : adiacenta[nod]) {
if (!vizitat[vecin.first])
{ Build(vecin.first , nod); }
}
}
void Init (int numar_noduri , int capat_1[] , int capat_2[] , int distanta[])
{
for (int indice = 0 ; indice < numar_noduri - 1 ; indice++)
{
adiacenta[capat_1[indice] + 1].emplace_back(capat_2[indice] + 1 , distanta[indice]);
adiacenta[capat_2[indice] + 1].emplace_back(capat_1[indice] + 1 , distanta[indice]);
}
BuildRMQ(1 , 0);
for (int exponent = 1 , putere = 2 ; putere <= tabel[0][0] ; exponent++ , putere <<= 1) {
for (int indice = 1 ; indice + putere - 1 <= tabel[0][0] ; indice++)
{ tabel[exponent][indice] = Combina(tabel[exponent - 1][indice] , tabel[exponent - 1][indice + (putere >> 1)]); }
}
//Build(1 , 0);
}
long long Query (int cantitate_1 , int sir_1[] , int cantitate_2 , int sir_2[])
{
long long rezultat = INT64_MAX;
for (int indice_1 = 0 ; indice_1 < cantitate_1 ; indice_1++) {
for (int indice_2 = 0 ; indice_2 < cantitate_2 ; indice_2++)
{ rezultat = min(rezultat , Distanta(sir_1[indice_1] + 1 , sir_2[indice_2] + 1)); }
}
return rezultat;
}
