#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
vector<int> g[maxn];
vector<int> klk(maxn);
vector<int> tren(maxn);
void dfs1(int cvor,int prosli=-1){
tren[cvor]=klk[cvor];
for(int i:g[cvor]){
if(i==prosli) continue;
dfs1(i,cvor);
tren[cvor]+=tren[i];
}
}
pair<int,int> dfs2(int cvor,int prosli=0){
pair<int,int> ovde={-1,cvor};
if(cvor!=prosli){
tren[prosli]-=tren[cvor];
tren[cvor]+=tren[prosli];
}
for(int i:g[cvor]) ovde=max(ovde,make_pair(tren[i],cvor));
for(int i:g[cvor]){
if(i==prosli) continue;
ovde=min(ovde,dfs2(i,cvor));
}
if(cvor!=prosli){
tren[cvor]-=tren[prosli];
tren[prosli]+=tren[cvor];
}
return ovde;
}
int LocateCentre(int n, int pp[], int s[], int d[]) {
for(int i=0;i<n;i++){
klk[i]=pp[i];
if(i<n-1){
g[s[i]].push_back(d[i]);
g[d[i]].push_back(s[i]);
}
}
dfs1(0);
return dfs2(0).second;
}
