#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
vector<int> E[N];
int siz[N];
int opt=2e9, sum, gdzie;
void dfs(int v, int p){
int res=0;
for(int u:E[v]){
if(u!=p){
dfs(u, v);
siz[v]+=siz[u];
res=max(res, siz[u]);
}
}
res=max(res, sum-siz[v]);
opt=min(opt, res);
if(res==opt)gdzie=v;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for(int i=0; i<N; i++){
siz[i]=pp[i];
sum+=siz[i];
}
for(int i=0; i<N-1; i++){
E[S[i]].push_back(D[i]);
E[D[i]].push_back(S[i]);
}
dfs(0, -1);
return gdzie;
}
