#include <bits/stdc++.h>
#define MAX 1210000
typedef std::pair<long long,long long> pii;
std::vector<long long> con[MAX];
long long res = 2e9+10;
long long ind;
int* pop;
long long soma_total = 0;
long long dfs(long long pos,long long prev,long long dist){
long long max = 0;
long long soma = pop[pos];
for(auto&x:con[pos]){
if(x!=prev){
long long r = dfs(x,pos,dist+(long long)pop[pos]);
max=std::max(max,r);
soma+=r;
}
}
max=std::max(max,soma_total-soma);
if(max<res){
res=std::min(res,max);
ind=pos;
}
return soma;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
pop=pp;
for(auto&x:con)x.clear();
res=2e9+10;
for(int i=0;i!=N-1;++i){
con[S[i]].push_back(D[i]);
con[D[i]].push_back(S[i]);
}
for(int i=0;i!=N;++i)soma_total+=pp[i];
int start = 0;
for(int i=0;i!=N;++i)if(con[i].size()==1)start=i;
dfs(start,-1,0);
return ind;
}
