#include <bits/stdc++.h>
#define DIM 1000010
#define INF 2000000000000000000LL
using namespace std;
vector <int> L[DIM];
long long sum[DIM];
int fth[DIM];
//int p[DIM],s[DIM],d[DIM];
//int n,i;
void dfs (int nod, int tata){
fth[nod] = tata;
for (auto vecin : L[nod])
if (vecin != tata){
dfs (vecin,nod);
sum[nod] += sum[vecin];
}
}
int LocateCentre (int n, int p[], int s[], int d[]){
for (int i=0;i<n-1;i++){
s[i]++, d[i]++;
L[s[i]].push_back(d[i]);
L[d[i]].push_back(s[i]);
}
long long sum_total = 0;
for (int i=1;i<=n;i++){
sum[i] = p[i-1];
sum_total += sum[i];
}
dfs (1,0);
long long mini = INF;
int sol = 0;
for (int i=1;i<=n;i++){
long long maxi = 0;
for (auto vecin : L[i]){
if (vecin == fth[i])
continue;
maxi = max (maxi,sum[vecin]);
}
maxi = max (maxi,sum_total - sum[i]);
if (maxi < mini){
mini = maxi;
sol = i;
}
}
return sol - 1;
}
