#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+56;
int n;
vector <int> g[N];
ll w[N];
ll subsum[N],celasuma = 0;
int najb = 0;
ll vr = 7e18;
void dfs(int x,int par){
subsum[x] = w[x];
ll cong = 0;
for(auto f : g[x]){
if(f == par) continue;
dfs(f,x);
cong = max(cong,subsum[f]);
subsum[x] += subsum[f];
}
cong = max(cong,celasuma-subsum[x]);
if(cong < vr){
vr = cong;
najb = x;
}
}
int LocateCentre(int br1,int *P,int *S,int *D){
n = br1;
for(int i = 0; i <= n; i++){
g[i].clear();
}
for(int i = 0; i < n; i++) w[i+1] = P[i];
for(int i = 0; i < n-1; i++){
g[S[i]+1].push_back(D[i]+1);
g[D[i]+1].push_back(S[i]+1);
}
celasuma = 0;
for(int i = 1; i <= n; i++) celasuma += w[i];
dfs(1,0);
return najb-1;
}
