#include "traffic.h"
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
#define pb push_back
#define ll long long
const int MAX = 1e6 + 7;
ll sz[MAX];
vector<int> adj[MAX];
inline ll dfs(int node, int par)
{
for (int to : adj[node])
if (to != par)
sz[node] += dfs(to, node);
return sz[node];
}
int LocateCentre(int N, int P[], int S[], int D[])
{
for (int i = 0; i < N-1; ++i)
adj[S[i]].pb(D[i]), adj[D[i]].pb(S[i]);
for (int i = 0; i < N; ++i)
sz[i] = P[i];
dfs(0, -1);
int res = -1;
ll best = 1e18;
for (int node = 0; node < N; ++node)
{
ll tmp = 0;
for (int to : adj[node])
{
ll ctr = sz[to];
if (sz[to] > sz[node])
ctr = sz[0] - sz[node];
tmp = max(tmp, ctr);
}
if (best > tmp)
best = tmp, res = node;
}
return res;
}
