#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
int LocateCentre(int n, int cnt[], int S[], int D[]) {
vector<vector<int>> g(n);
vector<int> under(n, 0), parrent(n, -1);
for (int i = 0; i < n - 1; i++) {
g[S[i]].push_back(D[i]);
g[D[i]].push_back(S[i]);
}
function<void(int, int)> dfs = [&] (int a, int p) {
parrent[a] = p;
under[a] = cnt[a];
for (auto &b : g[a]) {
if (b != p) {
dfs(b, a);
under[a] += under[b];
}
}
};
dfs(0, -1);
int mn = (int) 2e9 + 7, best = -1;
for (int i = 0; i < n; i++) {
int sol = 0;
for (auto &j : g[i]) {
if (j == parrent[i]) {
sol = max(sol, under[0] - under[i]);
} else {
sol = max(sol, under[j]);
}
}
if (sol < mn) {
best = i;
mn = sol;
}
}
assert(best != -1);
return best;
}
