#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using std::cout;
using std::endl;
using std::vector;
vector<int> city_sub_num;
vector<int> parent;
int calc_sub_fans(int at, int prev, int P[], const vector<vector<int>>& neighbors) {
city_sub_num[at] = P[at];
parent[at] = prev;
for (int n : neighbors[at]) {
if (n != prev) {
city_sub_num[at] += calc_sub_fans(n, at, P, neighbors);
}
}
return city_sub_num[at];
}
int LocateCentre(int N, int P[], int S[], int D[]) {
city_sub_num = vector<int>(N);
parent = vector<int>(N);
vector<vector<int>> neighbors(N);
for (int i = 0; i < N - 1; i++) {
neighbors[S[i]].push_back(D[i]);
neighbors[D[i]].push_back(S[i]);
}
calc_sub_fans(0, 0, P, neighbors);
int total_fans = 0;
for (int i = 0; i < N; i++) {
total_fans += P[i];
}
int min_congestion = INT_MAX;
int best_center = -1;
for (int i = 0; i < N; i++) {
int this_max = total_fans - city_sub_num[i];
for (int n : neighbors[i]) {
if (parent[i] != n) {
this_max = std::max(this_max, city_sub_num[n]);
}
}
if (this_max < min_congestion) {
min_congestion = this_max;
best_center = i;
}
}
return best_center;
}
