#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
int LocateCentre(int N, int pp[], int S[], int D[]) {
vector<vector<int>> edge(N);
for (int i = 0; i < N - 1; i++) {
edge[S[i]].push_back(D[i]);
edge[D[i]].push_back(S[i]);
}
vector<bool> vis(N);
vector<long long> sz(N);
auto dfs1 = [&](auto &&dfs, int u) -> void {
vis[u] = true;
sz[u] = pp[u];
for (int v : edge[u]) {
if (!vis[v]) {
dfs(dfs, v);
sz[u] += sz[v];
}
}
};
dfs1(dfs1, 0);
long long sum = 0;
for (int i = 0; i < N; i++) {
sum += pp[i];
}
vector<long long> val(N);
for (int u = 0; u < N; u++) {
for (int v : edge[u]) {
if (sz[v] < sz[u]) {
val[u] = max(val[u], sz[v]);
}
}
if (u > 0) {
val[u] = max(val[u], sum - sz[u]);
}
}
int mn = val[0], ret = 0;
for (int u = 1; u < N; u++) {
if (val[u] < mn) {
mn = val[u], ret = u;
}
}
return ret;
}
