#include<bits/stdc++.h>
#include "traffic.h"
#define fi first
#define se second
using namespace std;
const int NN=1e6;
vector<int> e[NN+10];
int siz[NN+10];
void dfs_siz(int x,int p)
{
for(auto v:e[x])
{
if(v!=p)
{
dfs_siz(v,x);
siz[x]+=siz[v];
}
}
return;
}
pair<int,int> dfs_min(int x,int p,int siz_all)
{
pair<int,int> ans={0,x};
for(auto v:e[x])
{
if(v==p)
ans.fi=max(ans.fi,siz_all-siz[x]);
else
ans.fi=max(ans.fi,siz[v]);
}
for(auto v:e[x])
{
if(v!=p)
ans=min(ans,dfs_min(v,x,siz_all));
}
return ans;
}
int LocateCentre(int N,int pp[],int S[],int D[])
{
for(int i=0;i<N-1;i++)
{
e[S[i]].push_back(D[i]);
e[D[i]].push_back(S[i]);
}
for(int i=0;i<N;i++)
siz[i]=pp[i];
dfs_siz(0,-1);
return dfs_min(0,-1,siz[0]).se;
}
