#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
constexpr int N = 1e6 + 1;
vector<int> a;
int64_t sz[N], parent[N];
vector<int> g[N];
void dfs(int u, int p) {
sz[u] += a[u];
parent[u] = p;
for (auto v : g[u]) {
if (v != p) {
dfs(v, u);
sz[u] += sz[v];
}
}
}
int LocateCentre(int n, int A[], int s[], int d[]) {
a.resize(n);
for (int i = 0; i < n; i++) {
a[i] = A[i];
}
for (int i = 0; i < n - 1; i++) {
g[s[i]].push_back(d[i]);
g[d[i]].push_back(s[i]);
}
dfs(0, -1);
int64_t sum = accumulate(a.begin(), a.end(), 0LL);
int mn = 2e9, ans = -1;
for (int u = 0; u < n; u++) {
int64_t cur = 0;
for (auto v : g[u]) {
if (v == parent[u]) {
cur = max(cur, sum - sz[u]);
} else {
cur = max(cur, sz[v]);
}
}
if (cur < mn) {
mn = cur;
ans = u;
}
}
return ans;
}
