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