#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 6;
int habs[MAXN];
int respNodo[MAXN];
struct newRoot
{
int nodo, padre, respPadre;
};
vector <int> ady[MAXN];
void dfs(int nodo, int padre)
{
int resp = 0;
for(auto i : ady[nodo])
{
if (i != padre)
{
dfs(i, nodo);
resp += respNodo[i];
}
}
resp += habs[nodo];
respNodo[nodo] = resp;
}
int LocateCentre(int N, int P[], int S[], int D[])
{
for (int i = 0; i < N; i++)
{
habs[i] = P[i];
}
for (int i = 0; i < N-1; i++)
{
ady[S[i]].push_back(D[i]);
ady[D[i]].push_back(S[i]);
}
//Enrizamos en 0
//nodo, padre, indice en la lista de adyacencia de mi padre
dfs(0, -1);
queue <newRoot> cola;
int minW = 2e9 + 10, idxOpt = 0;
int sum = 0;
int hl = -1;
for(auto i : ady[0])
{
sum += respNodo[i];
hl = max(hl, respNodo[i]);
}
sum += P[0];
minW = min(minW, hl);
for (auto i : ady[0])
{
cola.push({i, 0, sum - respNodo[i]});
}
while (!cola.empty())
{
newRoot curr = cola.front();
cola.pop();
int maxL = -1, sum = 0;
for(auto i : ady[curr.nodo])
{
if (i != curr.padre)
{
maxL = max(maxL, respNodo[i]);
sum += respNodo[i];
}else
{
maxL = max(maxL, curr.respPadre);
sum += curr.respPadre;
}
}
sum += P[curr.nodo];
if (maxL < minW)
{
minW = maxL;
idxOpt = curr.nodo;
}
for (auto i : ady[curr.nodo])
{
if (i != curr.padre)
{
cola.push({i, curr.nodo, sum - respNodo[i]});
}
}
}
return idxOpt;
//cout<<idxOpt<<endl;
}
