#include "traffic.h"
#include <vector>
#include <iostream>
#define vi vector<int>
using namespace std;
const int INF = 2000000100;
int A[1000001], DP[1000001];
vi adj[1000001];
int best = INF;
vi ans;
void DFS(int u, int p)
{
DP[u] = A[u];
for (const int &v : adj[u])
{
if (v == p) continue;
DFS(v, u);
DP[u] += DP[v];
}
}
void DFS2(int u, int p, int w)
{
int res = w;
for (const int &v : adj[u])
{
if (v == p) continue;
res = max(res, DP[v]);
}
if (res < best) {best = res; ans.clear();}
if (res == best) ans.push_back(u);
w += DP[u];
for (const int &v : adj[u])
{
if (v == p) continue;
DFS2(v, u, w - DP[v]);
}
}
int LocateCentre(int N, int P[], int S[], int D[])
{
for (int i = 0; i < N; i++) A[i] = P[i];
for (int i = 0; i + 1 < N; i++)
{
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
DFS(0, -1);
DFS2(0, -1, 0);
return ans[0];
}
