#include "traffic.h"
#include <vector>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
const int mx = 1'000'000;
const ll inf = 1'000'000'000'000'000'000LL;
int N;
vll pop(mx);
ll tot = 0;
vi edge[mx];
int res = -1;
ll cost = inf;
void dfs(int u, int p)
{
ll curr = 0;
for(int v : edge[u])
{
if(v == p)
continue;
dfs(v, u);
pop[u] += pop[v];
curr = max(curr, pop[v]);
}
curr = max(curr, tot - pop[u]);
if(curr < cost)
{
res = u;
cost = curr;
}
}
int LocateCentre(int N_, int pp[], int S[], int D[])
{
N = N_;
for(int i = 0; i < N; i++)
{
pop[i] = pp[i];
tot += pop[i];
}
for(int e = 0; e < N-1; e++)
{
edge[S[e]].push_back(D[e]);
edge[D[e]].push_back(S[e]);
}
dfs(0, -1);
return res;
}
