#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 1, INF = 2e9 + 2;
vector<int> adj[MAXN], population(MAXN), maxCongestion(MAXN), children(MAXN);
int total_people = 0;
void dfs(int s, int p)
{
for (auto u : adj[s])
{
if (u == p)
continue;
dfs(u, s);
children[s] += children[u];
maxCongestion[s] = max(maxCongestion[s], children[u]);
}
children[s] += population[s];
maxCongestion[s] = max(maxCongestion[s], total_people - children[s]);
}
int LocateCentre(int N, int P[], int S[], int D[])
{
for (int i = 0; i < N - 1; i++)
{
population[i] = P[i];
total_people += P[i];
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
population[N - 1] = P[N - 1];
total_people += P[N - 1];
dfs(0, -1);
int ans = -1, bestCongestion = INF;
for (int i = 0; i < N; i++)
{
if (maxCongestion[i] < bestCongestion)
{
ans = i;
bestCongestion = maxCongestion[i];
}
}
return ans;
}
