#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
const int maxn = 1e6+10;
int tot, mn, ans;
int a[maxn];
int sub[maxn];
vector<int> grafo[maxn];
void dfs(int u, int p)
{
sub[u] = a[u];
for (auto v: grafo[u])
{
if (v != p)
{
dfs(v, u);
sub[u] += sub[v];
}
}
}
void solve(int u, int p)
{
int aux = tot-sub[u];
for (auto v: grafo[u])
{
if (v != p)
{
aux = max(aux, sub[v]);
solve(v, u);
}
}
if (aux < mn)
{
ans = u;
mn = aux;
}
}
int LocateCentre(int N, int P[], int S[], int D[])
{
for (int i = 1; i <= N; i++)
grafo[i].clear();
for (int i = 1; i < N; i++)
{
S[i-1]++, D[i-1]++;
grafo[S[i-1]].push_back(D[i-1]);
grafo[D[i-1]].push_back(S[i-1]);
}
for (int i = 1; i <= N; i++)
{
a[i] = P[i-1];
tot += a[i];
}
mn = tot;
dfs(1, 0); solve(1, 0);
return ans-1;
}
