#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
const int NMAX = (int)1e6 + 1;
vector<int>ad[NMAX];
int sum[NMAX],A[NMAX],ans = (int)1e9,id = 0;
void dfs(int node,int parent) {
for (auto& x : ad[node])
if (x != parent) {
dfs(x,node);
sum[node] += sum[x];
}
}
void dfs1(int node,int parent,int sus) {
int cost = sus;
int cr = cost;
for (auto& x : ad[node])
if (x != parent) {
cost += sum[x];
cr = max(cr,sum[x]);
}
if (ans > cr) {
ans = cr;
id = node;
}
//cout << node << ' ' << parent << ' ' << sus << ' ' << cost << '\n';
for (auto& x : ad[node])
if (x != parent)
dfs1(x,node,cost - sum[x] + A[node]);
}
int LocateCentre(int N,int P[],int S[],int D[]) {
for (int i = 0; i < N;++i)
sum[i] = A[i] = P[i];
for (int i = 0; i < N - 1;++i) {
ad[S[i]].push_back(D[i]);
ad[D[i]].push_back(S[i]);
}
dfs(0,0);
dfs1(0,0,0);
return id;
}
