#include <bits/stdc++.h>
using namespace std;
static vector<int> edge[1000000];
static int V[1000000], sz[1000000], par[1000000];
static void dfs(int x, int p) {
par[x] = p;
sz[x] = V[x];
for (int i : edge[x]) {
if (i == p) continue;
dfs(i, x);
sz[x] += sz[i];
}
}
int LocateCentre(int n, int P[], int S[], int D[]) {
for (int i = 0; i < n; ++i) {
edge[i].clear();
V[i] = P[i];
}
for (int i = 0; i < n - 1; ++i) {
edge[S[i]].push_back(D[i]);
edge[D[i]].push_back(S[i]);
}
dfs(0, -1);
int ansv = 2e9 + 5, ansi = 0;
for (int i = 0; i < n; ++i) {
int mx = 0;
for (int j : edge[i]) {
mx = max(mx, par[i] == j ? sz[0] - sz[i] : sz[j]);
}
if (mx < ansv) ansv = mx, ansi = i;
}
return ansi;
}
