#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int sz[MAXN];
int val[MAXN];
int par[MAXN];
vector<int> adj[MAXN];
void dfs(int x, int p){
par[x] = p;
for (auto u : adj[x]){
if (u == p) continue;
dfs(u,x);
sz[x] += sz[u];
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
int tot = 0;
for (int i = 0; i<N; i++){
sz[i] = pp[i];
tot += pp[i];
}
for (int i = 0; i<N-1; i++){
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs(0,-1);
for (int i = 0; i<N; i++){
int ww = par[i];
int one = 0;
for (auto u : adj[i]){
if (u == ww) continue;
one = max(one, sz[u]);
}
int two = 0;
if (ww != -1){
two = tot - sz[i];
}
val[i] = max(one,two);
}
int idx = 0;
for (int i = 0; i<N; i++){
if (val[idx] > val[i]){
idx = i;
}
}
return idx;
}
