#include <iostream>
#include <vector>
using namespace std;
#define Int long long
const Int M = 1<<20;
vector<Int> nei[M];
Int Mx[M], Pop[M], cst[M], Ans, maxAns = 1e17;
void dfs(Int u, Int p){
cst[u] = Pop[u];
for (Int i : nei[u]){
if (i == p)
continue;
dfs(i, u);
cst[u] += cst[i];
Mx[u] = max(Mx[u], cst[i]);
}
}
void dfs2(Int u, Int p){
if (max(Mx[u], cst[p]) < maxAns)
Ans = u, maxAns = max(Mx[u], cst[p]);
for (Int i : nei[u]){
if (i == p)
continue;
cst[u] += cst[p] - cst[i];
dfs2(i, u);
cst[u] += cst[i] - cst[p];
}
}
int LocateCentre(int n, int p[], int s[], int d[]){
for (Int i=0;i<n-1;i++){
s[i]++;
d[i]++;
nei[s[i]].push_back(d[i]);
nei[d[i]].push_back(s[i]);
}
for (Int i=0;i<n;i++)
Pop[i+1] = p[i];
dfs(1, 0);
dfs2(1, 0);
return Ans - 1;
}
