#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>v[1000000];
long long c[1000000],m[1000000];
void dfs(int x,int from){
for(int i:v[x]){
if(i==from)continue;
dfs(i,x);
c[x]+=c[i];
}
}
int LocateCentre(int N, int P[], int S[], int D[]) {
for(int i=0;i<N-1;i++){
v[S[i]].push_back(D[i]);
v[D[i]].push_back(S[i]);
}
for(int i=0;i<N;i++){
c[i]=P[i];
}
dfs(0,0);
for(int i=0;i<N-1;i++){
if(c[S[i]]<c[D[i]])swap(S[i],D[i]);
m[S[i]]=max(m[S[i]],c[D[i]]);
m[D[i]]=max(m[D[i]],c[0]-c[D[i]]);
}
pair<long long,int>res={0xE869120E869120,-1};
for(int i=0;i<N;i++){
res=min(res,{m[i],i});
}
return res.second;
}
