#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 1e6+10;
ll dp[mxN], pop[mxN];
vector<int> adj[mxN];
ll sum = 0;
ll ans = 1e18, last = -1;
void dfs(int node, int p) {
for(auto it : adj[node]) {
if(it == p) continue;
dfs(it, node);
dp[node] += dp[it];
}
dp[node] += pop[node];
ll mx = sum-dp[node];
for(auto it : adj[node]) {
if(it == p) continue;
mx = max(mx, dp[it]);
}
if(mx < ans) {
ans = mx;
last = node;
}
}
int LocateCentre(int n, int p[], int s[], int d[]) {
for(int i = 0; i < n-1; i++) {
adj[s[i]].push_back(d[i]);
adj[d[i]].push_back(s[i]);
}
for(int i = 0; i < n; i++) {
sum += p[i];
pop[i] = p[i];
}
dfs(0, -1);
return last;
}
/*
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int p[10], s[10], d[10];
for(int i = 0; i < n; i++) {
cin >> p[i];
}
for(int i = 0; i < n-1; i++) {
cin >> s[i];
}
for(int i = 0; i < n-1; i++) {
cin >> d[i];
}
cout << LocateCentre(n, p, s, d);
return 0;
}*/
