#include "traffic.h"
#include <vector>
#include <iostream>
const int N = 1000000 + 100;
std::vector<int> g[N];
int sz[N];
int pr[N];
void dfs(int v) {
for (int to : g[v]) if (to != pr[v]) {
pr[to] = v;
dfs(to);
sz[v] += sz[to];
}
}
int LocateCentre(int N, int p[], int S[], int D[]) {
for (int i = 0; i < N; i++)
sz[i] = p[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);
int ver = 0, mx = 0;
for (int to : g[ver]) mx = std::max(mx, sz[to]);
for (int i = 1; i < N; i++) {
int val = 0;
for (int to : g[i]) if (to != pr[i])
val = std::max(val, sz[to]);
val = std::max(val, sz[0] - sz[i]);
if (val < mx) {
mx = val;
ver = i;
}
}
return ver;
}
