#include "traffic.h"
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
using ll = long long;
int LocateCentre(int N, int pp[], int S[], int D[]) {
if (N == 1)
return 0;
vector<vector<int>> adj(N);
for (int i = 0; i < N - 1; i++) {
adj[S[i]].push_back(D[i]), adj[D[i]].push_back(S[i]);
}
vector<ll> stree(N);
multiset<ll> msi;
vector<int> in(N);
vector<pair<int, int>> vpii;
vpii.emplace_back(0, 0);
while (!vpii.empty()) {
A:
auto &[cur, par] = vpii.back();
B:
if (in[cur] < adj[cur].size()) {
if (adj[cur][in[cur]] == par) {
in[cur]++;
goto B;
}
vpii.emplace_back(adj[cur][in[cur]++], cur);
goto A;
}
stree[cur] = pp[cur];
for (auto a : adj[cur]) {
if (a != par) {
stree[cur] += stree[a];
// cout << cur << " " << a << "\n";
msi.insert(stree[a]);
}
}
vpii.pop_back();
}
// for (auto a : stree)
// cout << a << " ";
// cout << "\n";
// for (auto a : msi)
// cout << a << " ";
// cout << "\n";
ll tot = accumulate(pp, pp + N, 0ll);
ll mini = *msi.rbegin();
int ans = 0;
function<void(int, int)> fvvi2 = [&](int cur, int par) {
if (*msi.rbegin() < mini) {
ans = cur;
mini = *msi.rbegin();
}
for (auto a : adj[cur]) {
if (a != par) {
msi.erase(msi.find(stree[a]));
msi.insert(tot - stree[a]);
fvvi2(a, cur);
msi.insert(stree[a]);
msi.erase(msi.find((tot - stree[a])));
}
}
};
fvvi2(0, 0);
return ans;
}
