#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
int LocateCentre(int N, int pp[], int S[], int D[]) {
vector<vector<int>> adj(N);
for (int i = 0; i < N-1; i++) {
int u = S[i], v = D[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<ll> sum(N);
auto solve = [&](auto &&solve, int u, int p) -> void {
sum[u] += pp[u];
for (auto &v : adj[u]) {
if (v != p) {
solve(solve, v, u);
sum[u] += sum[v];
}
}
};
solve(solve, 0, 0);
vector<ll> cand(N);
auto work = [&](auto &&work, int u, int p) -> void {
cand[u] = sum[0] - sum[u];
for (auto &v : adj[u]) {
if (v != p) {
cand[u] = max(cand[u], sum[v]);
work(work, v, u);
}
}
};
work(work, 0, 0);
vector<int> o(N);
iota(o.begin(), o.end(), 0);
sort(o.begin(), o.end(), [&](int i, int j) {
if (cand[i] == cand[j]) return i < j;
return cand[i] < cand[j];
});
// for (int i = 0; i < N; i++) {
// cerr << i sp cand[i] << endl;
// }
return o[0];
}
