// source: https://oj.uz/problem/view/IOI10_traffic
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN = 1000000;
int n, ans, a[mxN], sz[mxN], mx[mxN];
vector<int> adj[mxN];
void dfs(int u = 0, int p = -1) {
sz[u] = a[u];
mx[u] = 0;
for (int v : adj[u]) if (v != p) {
dfs(v, u);
sz[u] += sz[v];
mx[u] = max(mx[u], sz[v]);
}
}
void dfs2(int u = 0, int p = -1) {
if (ans == -1 || mx[u] < mx[ans]) ans = u;
for (int v : adj[u]) if (v != p) {
mx[v] = max(mx[v], sz[0] - sz[v]);
dfs2(v, u);
}
}
int LocateCentre(int _n, int p[], int s[], int d[]) {
n = _n;
for (int i = 0; i < n; ++i) a[i] = p[i];
for (int i = 0; i < n - 1; ++i) {
adj[s[i]].push_back(d[i]);
adj[d[i]].push_back(s[i]);
}
ans = -1;
dfs();
dfs2();
// for (int i = 0; i < n; ++i) cout << mx[i] << " ";
return ans;
}
/*
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n = 5;
int p[5] = {10, 10, 10, 20, 20};
int s[4] = {0, 1, 2, 3};
int d[4] = {2, 2, 3, 4};
cout << LocateCentre(n, p, s, d);
return 0;
}
*/
