#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void dfs1(vector<vector<int>>& gr,vector<ll>& w,vector<ll>& st,vector<int>& pa,int u,int p) {
st[u]=w[u];
pa[u]=p;
for(int v:gr[u]) {
if(v==p) continue;
dfs1(gr,w,st,pa,v,u);
st[u]+=st[v];
}
}
void dfs2(vector<vector<int>>& gr,vector<ll>& st,vector<ll>& pw,int u,int p) {
for(int v:gr[u]) {
if(v==p) continue;
pw[v]=pw[u]+st[u]-st[v];
dfs2(gr,st,pw,v,u);
}
}
int LocateCentre(int N,int P[],int S[],int D[]) {
vector<vector<int>> gr(N);
for(int i=0;i<N-1;++i) {
gr[S[i]].push_back(D[i]);
gr[D[i]].push_back(S[i]);
}
vector<ll> w(P,P+N),st(N),pw(N),mw(N);
vector<int> pa(N);
dfs1(gr,w,st,pa,0,0);
pw[0]=0;
dfs2(gr,st,pw,0,0);
ll cmw=LLONG_MAX;
int ans=0;
for(int u=0;u<N;++u) {
ll mw=pw[u];
for(int v:gr[u]) if(v!=pa[u]) mw=max(mw,st[v]);
if(mw<cmw) {
ans=u;
cmw=mw;
}
}
return ans;
}
