#include <bits/stdc++.h>
using namespace std;
const int MX = 1e6;
const int INF = 2e9+1;
int fans = 0;
int nodes[MX], people[MX], child[MX];
vector<vector<int>> adj(MX);
void dfs(int parent, int node) {
int tmp = 0;
for (auto& u: adj[node]) {
if (u == parent) continue;
tmp += nodes[u];
dfs(node, u);
tmp += child[u];
child[node] += tmp;
people[node] = max(people[node], child[u] + nodes[u]);
}
people[node] = max(people[node], fans - tmp - nodes[node]);
}
int LocateCentre(int N, int P[], int S[], int D[]) {
for (int i = 0; i < N; ++i) {
fans += (nodes[i] = P[i]);
if (i < N-1) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
}
dfs(-1,0);
int ans = 0, minC = INF;;
for (int i = 0; i < N; ++i) {
if (minC > people[i]) {
ans = i;
minC = people[i];
}
}
return ans;
}
//int main() {
//ios_base::sync_with_stdio(false); cin.tie(nullptr);
//int N = 5, P[] = {10,10,10,20,20}, S[] = {0,1,2,3}, D[] = {2,2,3,4};
//cout << LocateCentre(N,P,S,D) << "\n";
//}
