#include <bits/stdc++.h>
//#include "grader.cpp"
#include "traffic.h"
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
#define pb push_back
vll sz, dp1, dp2;
vvi adj;
int n;
ll total=0;
void dfs1(int u, int par=-1){
for (int v : adj[u]){
if (v == par) continue;
dfs1(v, u);
sz[u] += sz[v];
dp1[u] += dp1[v];
dp1[u] += sz[v];
}
}
void dfs2(int u, int par=-1){
dp2[u] = dp1[u];
if (par > -1){
dp2[u] += dp2[par] - dp1[u] - sz[u];
dp2[u] += total - sz[u];
}
for (int v : adj[u]){
if (v != par){
dfs2(v, u);
}
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
n = N;
sz = dp1 = dp2 = vll(n, 0);
for (int i=0; i<n; i++){
sz[i] = pp[i];
total += sz[i];
}
adj.assign(n, {});
for (int i=0; i<n-1; i++){
adj[S[i]].pb(D[i]);
adj[D[i]].pb(S[i]);
}
dfs1(0);
dfs2(0);
int ans = 0;
for (int i=1; i<n; i++){
if (dp2[i] < dp2[ans]){
ans = i;
}
}
return ans;
}
