#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1000000];
int par[1000000];
int acc[1000000];
int p_sum;
int dfs(int N, int P[], int u, int p)
{
par[u] = p;
acc[u] = P[u];
for (const int &v : adj[u])
{
if (v != p)
acc[u] += dfs(N, P, v, u);
}
return acc[u];
}
int LocateCentre(int N, int P[], int S[], int D[])
{
p_sum = 0;
for (int i = 0; i < N; i++)
p_sum += P[i];
for (int j = 0; j < N - 1; j++)
adj[S[j]].push_back(D[j]),
adj[D[j]].push_back(S[j]);
int s = -1;
for (int i = 0; i < N; i++)
{
if (adj[i].size() == 1)
{
s = i;
break;
}
}
dfs(N, P, s, -1);
int city = -1;
int min_traffic = INT_MAX;
for (int i = 0; i < N; i++)
{
int traffic = 0;
for (const int &v : adj[i])
{
if (v == par[i])
traffic = max(traffic, p_sum - acc[i]);
else
traffic = max(traffic, acc[v]);
}
if (traffic < min_traffic)
{
city = i;
min_traffic = traffic;
}
}
return city;
}
