#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
ll dfs(int S, int padre, vector<vector<int>> & listaAdyacencia, vector<ll> & DP) {
for (int v: listaAdyacencia[S]) {
if (v == padre)
continue;
DP[S] += dfs(v, S, listaAdyacencia, DP);
}
// DP[S] contiene la suma de las poblaciones del subárbol de S
return DP[S];
}
int LocateCentre(int N, int P[], int S[], int D[]) {
vector<ll>DP(N);
vector<vector<int>> listaAdyacencia(N, vector<int>());
for (int i = 0; i < N-1; i++) {
// pasamos el formato de entrada a una lista de adyacencia, más cómodo para operar
// al ser aristas bidireccionales, las añadimos en ambas direcciones
listaAdyacencia[S[i]].emplace_back(D[i]);
listaAdyacencia[D[i]].emplace_back(S[i]);
}
for (int i = 0; i < N; i++)
DP[i] = P[i]; // inicializamos la DP para que contenga la población de cada ciudad
// rellenamos la DP
dfs(0, -1, listaAdyacencia, DP);
// por defecto, elegimos 0 como ciudad arbitrariamente y encontramos la máxima congestión
int ciudadElegida = 0;
ll maximaCongestionCiudadElegida = 0;
for (int vecinoRaiz: listaAdyacencia[0]) {
maximaCongestionCiudadElegida = max(maximaCongestionCiudadElegida, DP[vecinoRaiz]);
}
ll maximaCongestionCiudadActual;
for (int ciudadActual = 1; ciudadActual < N; ciudadActual++) {
maximaCongestionCiudadActual = DP[0] - DP[ciudadActual];
for (int v: listaAdyacencia[ciudadActual]) {
if (DP[v] < DP[ciudadActual])
maximaCongestionCiudadActual = max(maximaCongestionCiudadActual, DP[v]);
}
if (maximaCongestionCiudadActual < maximaCongestionCiudadElegida) {
maximaCongestionCiudadElegida = maximaCongestionCiudadActual;
ciudadElegida = ciudadActual;
}
}
return ciudadElegida;
}
