#include "traffic.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 1e6+10;
vector<int> A[N];
int cnt[N];
int par[N];
int *p;
int n;
int dfs(int v, int p)
{
par[v] = p;
cnt[v] = ::p[v];
for (int u : A[v])
if (u != p)
cnt[v] += dfs(u, v);
return cnt[v];
}
int LocateCentre(int N, int pp[], int v[], int u[])
{
n = N;
p = pp;
Loop (i,0,n-1) {
A[v[i]].push_back(u[i]);
A[u[i]].push_back(v[i]);
}
dfs(0, -1);
int ans = 2e9;
int vans = 0;
Loop (v,0,n) {
int x = 0;
for (int u : A[v])
x = max(x, u == par[v]? cnt[0]-cnt[v]: cnt[u]);
if (x < ans) {
vans = v;
ans = x;
}
}
return vans;
}
