#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int N=1e6;
vector<int> adj[N];
ll dp[N];
ll sum[N];
void dfs0(int u=0,int e=-1) {
for (int &v: adj[u]) if (v!=e) {
dfs0(v,u);
cmax(dp[u],sum[v]);
sum[u]+=sum[v];
}
}
void dfs1(int u=0,int e=-1) {
for (int &v: adj[u]) if (v!=e) {
cmax(dp[v],dp[0]-sum[v]);
dfs1(v,u);
}
}
int LocateCentre(int n, int _w[], int s[], int e[]) {
for (int i=0;i<n-1;i++) {
adj[s[i]].push_back(e[i]);
adj[e[i]].push_back(s[i]);
}
for (int i=0;i<n;i++) {
sum[i]=_w[i];
}
dfs0();
dfs1();
ll mx = 1e18;
int res = -1;
for (int i=0;i<n;i++) {
if (cmin(mx,dp[i])) {
res = i;
}
}
assert(res!=-1);
return res;
}
