#include "traffic.h"
#include "bits/stdc++.h"
using namespace std;
const int mxN = 1e6 + 7;
int n, p[mxN], dp[mxN], ans[mxN], tot;
vector<int> graph[mxN];
void dfs(int u, int par) {
dp[u] = p[u];
for (auto v : graph[u]) {
if (v != par) {
dfs(v, u);
dp[u] += dp[v];
ans[u] = max(ans[u], dp[v]);
}
}
}
int LocateCentre(int N, int P[], int S[], int D[]) {
n = N;
for (int i = 0; i < n; ++i) {
p[i] = P[i];
tot += p[i];
}
for (int i = 0; i < n - 1; ++i) {
graph[S[i]].push_back(D[i]);
graph[D[i]].push_back(S[i]);
}
dfs(0, -1);
int res = INT_MAX, city = 0;
for (int u = 0; u < n; ++u) {
int val = max(tot - dp[u], ans[u]);
if (res > val) {
res = val;
city = u;
}
}
return city;
}
