#include <bits/stdc++.h>
using namespace std;
void fastIO() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
const int NMAX = 1e6;
int a[NMAX], dp[NMAX], sum[NMAX];
vector<int> G[NMAX];
void dfs(int u, int parent) {
sum[u] = a[u];
for (int v : G[u])
if (v != parent) {
dfs(v, u);
sum[u] += sum[v];
if (sum[v] > dp[u])
dp[u] = sum[v];
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for (int i = 0; i < N - 1; ++i) {
G[S[i]].emplace_back(D[i]);
G[D[i]].emplace_back(S[i]);
}
for (int u = 0; u < N; ++u)
a[u] = pp[u];
dfs(0, -1);
int ans = 0;
for (int u = 0; u < N; ++u) {
if (sum[0] - sum[u] > dp[u])
dp[u] = sum[0] - sum[u];
if (dp[u] < dp[ans])
ans = u;
}
return ans;
}
/*int N, P[NMAX], S[NMAX], D[NMAX];
int main() {
fastIO();
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';
return 0;
} */
