#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
static int N,P[1000000],S[1000000],D[1000000];
vector<int>tree[1000000];
int subsz[1000000];
int get_subsz(int nod,int tata,int pp[]){
subsz[nod]=pp[nod];
for(auto fiu : tree[nod])
if(fiu!=tata)
subsz[nod]+=get_subsz(fiu,nod,pp);
return subsz[nod];
}
void add_edge(int u,int v){
tree[u].push_back(v);
tree[v].push_back(u);
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
int i;
for(i=0;i<N-1;++i)
add_edge(S[i],D[i]);
get_subsz(0,-1,pp);
int raspnod=-1;
int raspsz=2e9+1;
for(i=0;i<N;++i){
int maxim=0;
for(auto fiu : tree[i])
if(subsz[i]>subsz[fiu] && maxim<subsz[fiu])
maxim=subsz[fiu];
if(maxim<subsz[0]-subsz[i])
maxim=subsz[0]-subsz[i];
if(raspsz>maxim){
raspsz=maxim;
raspnod=i;
}
}
return raspnod;
}
