#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define id pair<ll,vector<ll> >
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "traffic.h"
vector<vector<ll> > adj;
ll sum = 0;
ll ex[1000005];
ll sumi[100005] = {0};
int ans = 0;
ll res = 2e9+5;
void build(ll idx,ll p){
sumi[idx] += ex[idx];
for(auto x:adj[idx]){
if(x != p){
build(x,idx);
sumi[idx] += sumi[x];
}
}
}
void solve(ll idx,ll p){
ll resi = 0;
ll sumd = 0;
for(auto x:adj[idx]){
if(x != p){
solve(x,idx);
resi = max(resi,sumi[x]);
sumd += sumi[x];
}
}
sumd += ex[idx];
resi = max(resi,sum - sumd);
if(resi < res){
res = resi;
ans = idx;
}
}
int LocateCentre(int n, int arr[], int a[], int b[]){
adj.assign(n+5,vector<ll>());
f(i,0,n-1){
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
f(i,0,n){
ex[i] = arr[i];
sum += ex[i];
}
build(0,0);
solve(0,0);
return ans;
}
