#include "traffic.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long
#define all(x) x.begin(),x.end()
const int MAX = 1e6+10 ;
const int inf = 2e9+10 ;
using namespace std ;
int mn = inf , idx ;
int sub[MAX] ;
vector<int> adj[MAX] ;
bool spun[MAX] ;
void dfs1(int x, int dad=-1)
{
for(auto e : adj[x] )
if(e != dad)
{
dfs1(e, x) ;
sub[x] += sub[e] ;
}
}
void dfs2(int x)
{
spun[x] = true ;
int saveSub = sub[x] ;
int myMx = 0 ;
for(auto e : adj[x] )
myMx = max(myMx , sub[e] ) ;
if(myMx < mn )
{
mn = myMx ;
idx = x ;
}
for(auto e : adj[x] )
{
if( spun[e] ) continue ;
int saveE = sub[e] ;
sub[x] -= sub[e];
sub[e] = saveSub ;
dfs2(e) ;
sub[e] = saveE ;
sub[x] = saveSub ;
}
}
int LocateCentre(int N, int pp[], int S[], int D[])
{
lp(i,0,N) sub[i] += pp[i] ;
lp(i,0,N-1)
{
int u = S[i] ;
int v = D[i] ;
adj[u].pb(v) ;
adj[v].pb(u) ;
}
dfs1(0,-1) ;
dfs2(0) ;
return idx ;
}
