#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e6 + 9;
const ll inf = 1e9 + 7;
const ll Log2 = 20;
typedef pair<ll,ll> LL;
vector<ll> g[N],euler;
ll n,a[N],mn = inf,chosen,child[N],InitChild[N],sum;
set<LL> s[N];
void DFSinit(ll u,ll p){
child[u] = a[u];
for (auto i : g[u]){
if (i == p) continue;
DFSinit(i,u); child[u] += child[i];
s[u].insert({child[i],i});
}
InitChild[u] = child[u];
}
void DFS(ll u,ll p){
LL now = *s[u].rbegin(),rm = {sum - child[u],-1};
now = max(now,rm);
if (now.fs < mn) mn = now.fs,chosen = u;
for (auto i : g[u]){
if (i == p) continue;
s[u].erase({child[i],i}); s[i].insert({sum - child[i],u});
//cout<<child[i]<<" "<<i; exit(0);
child[u] = sum - child[i]; child[i] = sum;
DFS(i,u);
}
if (p >= 0){
child[u] = InitChild[u];
s[p].insert({child[u],u}); s[u].erase({child[p],p});
child[p] = InitChild[p];
}
}
ll LocateCentre(ll sz,ll P[],ll X[],ll Y[]){
n = sz;
for (ll i = 0;i < n;i++) a[i] = P[i],sum += a[i];
for (ll i = 0;i < n - 1;i++){
g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]);
}
DFSinit(0,-1); DFS(0,-1);
return chosen;
}
