#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> sz, mx;
void dfs(int u, int p)
{
for (int v: g[u])
{
if (v==p) continue;
dfs(v,u);
sz[u] += sz[v];
mx[u] = max(mx[u],sz[v]);
}
}
int LocateCentre(int N, int P[], int S[], int D[])
{
g.resize(N);
sz.resize(N);
mx.resize(N);
for (int i=0;i<N;i++) sz[i] = P[i];
for (int i=0;i+1<N;i++)
{
g[S[i]].push_back(D[i]);
g[D[i]].push_back(S[i]);
}
dfs(0,-1);
int SS = sz[0];
int Q = -1, bst = SS+1;
for (int i=0;i<N;i++)
{
if (mx[i]<SS-sz[i]) mx[i] = SS-sz[i];
if (bst>mx[i]) bst = mx[i], Q = i;
}
return Q;
}
