/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
typedef long long ll;
const int N_MAX = 1000000;
int n;
int p[N_MAX];
int subSize[N_MAX];
vector <int> edges[N_MAX];
int parent[N_MAX];
void dfs (int u)
{
subSize[u] = p[u];
for(int v : edges[u])
if(v != parent[u])
{
parent[v] = u;
dfs(v);
subSize[u] += subSize[v];
}
}
int LocateCentre (int N, int P[], int X[], int Y[])
{
n = N;
for(int u = 0; u < n; u++)
p[u] = P[u];
for(int i = 0; i < n - 1; i++)
{
edges[X[i]].push_back(Y[i]);
edges[Y[i]].push_back(X[i]);
}
parent[0] = -1;
dfs(0);
int best = INT_MAX;
int answer = -1;
for(int u = 0; u < n; u++)
{
int maxFlow = subSize[0] - subSize[u];
for(int v : edges[u])
if(v != parent[u])
maxFlow = max(maxFlow, subSize[v]);
if(maxFlow < best)
{
best = maxFlow;
answer = u;
}
}
for(int i = 0; i < n; i++)
edges[i].clear();
return answer;
}
