#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> g[1000005];
long long num[1000005],minv=1000000000000000000;
int n,ans;
long long DFS(int v,int p){
for(auto x:g[v])
if(x!=p)
num[v]+=DFS(x,v);
return num[v];
}
void DP(int v,int p){
for(auto x:g[v]){
if(x==p)
continue;
long long pre=num[v];
num[v]-=num[x];
num[x]+=pre;
DP(x,v);
num[x]-=pre;
num[v]+=num[x];
}
long long maxv=0;
for(auto x:g[v])
if(x!=p)
maxv=max(maxv,num[x]);
if(maxv<minv){
minv=maxv;
ans=v;
}
}
int LocateCentre(int N,int *P,int *S,int *D){
int i;
n=N;
for(i=0;i<n;i++)
num[i]=P[i];
for(i=0;i<n-1;i++){
g[S[i]].emplace_back(D[i]);
g[D[i]].emplace_back(S[i]);
}
DFS(0,-1);
DP(0,-1);
return ans;
}
