#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }
const int MAXN = 1e6 + 5;
vector<int> g[MAXN];
int p[MAXN], dpPar[MAXN], node = 1;
ll sum[MAXN], tot = 0, ans = 1e18;
void dfs(int u, int pa) {
ll res = 0;
sum[u] = p[u];
for (int v : g[u]) {
if (v != pa) {
dfs(v, u);
sum[u] += sum[v];
ckmax(res, sum[v]);
}
}
ckmax(res, tot - sum[u]);
if (ckmin(ans, res)) node = u;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
memcpy(p, pp, N * sizeof(int));
for (int i = 0; i < N - 1; i++) {
g[S[i]].emplace_back(D[i]);
g[D[i]].emplace_back(S[i]);
}
tot = accumulate(p, p + N, 0LL);
dfs(0, 0);
return node;
}
