#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1000005;
vector<int> adj[MAXN];
long long subtree_sum[MAXN];
int fans[MAXN];
long long total_fans = 0;
long long min_congestion = 3e18; // Juda katta son
int result_city = 0;
// Har bir shoxchani (subtree) umumiy muxlislar sonini hisoblash
void dfs_sum(int u, int p) {
subtree_sum[u] = fans[u];
for (int v : adj[u]) {
if (v != p) {
dfs_sum(v, u);
subtree_sum[u] += subtree_sum[v];
}
}
}
// Har bir shaharni arena deb tekshirib ko'rish
void dfs_solve(int u, int p) {
long long max_val = 0;
// Pastki shoxchalardagi tirbandlik
for (int v : adj[u]) {
if (v != p) {
max_val = max(max_val, subtree_sum[v]);
dfs_solve(v, u);
}
}
// Yuqori (ota) tomondan keladigan tirbandlik
long long upper_part = total_fans - subtree_sum[u];
max_val = max(max_val, upper_part);
// Eng kichik maksimal tirbandlikni topish
if (max_val < min_congestion) {
min_congestion = max_val;
result_city = u;
}
}
int LocateCentre(int N, int P[], int S[], int D[]) {
total_fans = 0;
for (int i = 0; i < N; i++) {
adj[i].clear();
fans[i] = P[i];
total_fans += P[i];
}
for (int i = 0; i < N - 1; i++) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs_sum(0, -1);
dfs_solve(0, -1);
return result_city;
}
