#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
void dfs(int node, int parent, vector<vector<int>> & adjList, vector<ll> & subtreePopulation){
for (int neighbour: adjList[node]){
if (neighbour == parent)
continue;
dfs(neighbour, node, adjList, subtreePopulation);
subtreePopulation[node] += subtreePopulation[neighbour];
}
}
int chooseCity(vector<vector<int>> & adjList, vector<ll> & subtreePopulation){
int N = (int)adjList.size();
int chosenCity = 0;
ll chosenCityMaxConjestion = 0;
for (int rootNeighbour: adjList[0]){
chosenCityMaxConjestion = max(chosenCityMaxConjestion, subtreePopulation[rootNeighbour]);
}
for (int currentCity=1;currentCity<N;currentCity++){
ll currentCityMaxConjestion = subtreePopulation[0] - subtreePopulation[currentCity];
for (int neighbour: adjList[currentCity]){
if (subtreePopulation[neighbour]<subtreePopulation[currentCity]){
currentCityMaxConjestion = max(currentCityMaxConjestion, subtreePopulation[neighbour]);
}
}
if (chosenCityMaxConjestion > currentCityMaxConjestion){
chosenCityMaxConjestion = currentCityMaxConjestion;
chosenCity = currentCity;
}
}
return chosenCity;
}
int LocateCentre(int N, int P[], int S[], int D[] ){
vector<vector<int>> adjList(N);
vector<ll> subtreePopulation(N);
for (int i=0;i<N-1;i++){
adjList[S[i]].emplace_back(D[i]);
adjList[D[i]].emplace_back(S[i]);
}
for (int i=0;i<N;i++){
subtreePopulation[i] = P[i];
}
dfs(0, -1, adjList, subtreePopulation);
return chooseCity(adjList, subtreePopulation);
}
