#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
long long val[1000005],subtree[1000005],ans=1000000000000000000,calc[1000005];
vector<int>g[1000005];
void dfs(int node,int p)
{
subtree[node]=val[node];
for(int go:g[node])
if(go!=p)dfs(go,node),subtree[node]+=subtree[go];
}
void answer(int node,int p)
{
//cout<<ans<<endl;
//long long calc=0;
for(int go:g[node])
{
if(go!=p)
{
calc[node]=max(calc[node],subtree[go]);
answer(go,node);
}
else calc[node]=max(calc[node],subtree[1]-subtree[node]);
}
ans=min(ans,calc[node]);
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for(int i=1;i<=N;i++)val[i]=pp[i-1];
//for(int i=1;i<=N;i++)cout<<val[i]<<" ";cout<<endl;
for(int i=0;i<N-1;i++)
g[S[i]+1].push_back(D[i]+1),g[D[i]+1].push_back(S[i]+1);
dfs(1,0);
//for(int i=1;i<=N;i++)cout<<subtree[i]<<" ";cout<<endl;
answer(1,0);
for(int i=1;i<=N;i++)if(calc[i]==ans)return i-1;
return 0;
}
