#include "traffic.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 1e6 + 10;
const int INF = 1e9;
int n;
int sz[MAXN];
std::vector <int> g[MAXN];
void dfs(int node, int par)
{
sz[node] = 1;
for (const int &u : g[node])
{
if (u == par)
{
continue;
}
dfs(u, node);
sz[node] += sz[u];
}
}
int find(int node, int par)
{
for (const int &u : g[node])
{
if (u == par)
{
continue;
}
if (sz[u] > n / 2)
{
return find(u, node);
}
}
return node;
}
int LocateCentre(int N, int pp[], int S[], int D[])
{
n = N;
for (int i = 0 ; i < n - 1 ; ++i)
{
g[S[i]].push_back(D[i]);
g[D[i]].push_back(S[i]);
}
dfs(0, -1);
return find(0, -1);
}
