#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 20;
vector<int> adj[maxn];
int sum[maxn];
int par[maxn];
int a[maxn];
void dfs(int u) {
sum[u] = a[u];
for (auto v: adj[u]) {
if (v != par[u]) {
par[v] = u;
dfs(v);
sum[u] += sum[v];
}
}
}
int LocateCentre(int n, int _a[], int S[], int D[]) {
for (int i = 1; i <= n; i++) {
a[i] = _a[i - 1];
}
for (int i = 0; i < n - 1; i++) {
int u = S[i] + 1;
int v = D[i] + 1;
adj[u].push_back(v);
adj[v].push_back(u);
}
par[1] = -1;
dfs(1);
pair<int, int> res = make_pair(2e9 + 20, -1);
for (int u = 1; u <= n; u++) {
int mx = 0;
for (auto v: adj[u]) {
if (v != par[u]) {
mx = max(mx, sum[v]);
}
}
mx = max(mx, sum[1] - sum[u]);
res = min(res, make_pair(mx, u));
}
return res.second - 1;
}
