#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> path[1000005];
int visited[1000005];
int ppl[1000005];
int solve(int u){
int sum=0;
for(auto &[v,w]:path[u]){
if(visited[v])continue;
visited[v]=true;
w=solve(v);
sum+=w;
}
return sum+ppl[u];
}
int LocateCentre(int n, int people[], int S[], int D[]) {
#define int long long
for(int i=0;i<n;i++){
path[i].clear();
visited[i]=false;
ppl[i]=people[i];
}
for(int i=0;i<n-1;i++){
path[S[i]].push_back({D[i],0});
path[D[i]].push_back({S[i],0});
}
visited[0]=1;
solve(0);
int mn=1e18,best=2e18;
int u=0,prev=-1;
int nxt=0;
/*for(int i=0;i<n;i++){
for(auto [v,w]:path[i]){
cout << i << " " <<v << " :: "<< w << endl;
}
}*/
while(mn<best){
best=mn;
prev=u;
u=nxt;
//find max vertex
int maxvertex=-1;
int sum=0;
for(auto &[v,w]:path[u]){
if(w>maxvertex){
nxt=v;
maxvertex=w;
}
sum+=w;
}
//
mn=maxvertex;
// prepare for nxt to be the next one
for(auto &[v,w]:path[nxt]){
if(v==u){
w=(sum-maxvertex+people[u]);
//cout << "UPDATED";
break;
}
}
/*for(int i=0;i<n;i++){
for(auto [v,w]:path[i]){
cout << i << " " <<v << " :: "<< w << endl;
}
}*/
//cout << "Maxver " << maxvertex << " best " << best << " mn " << mn << " AT " <<u << " MOVING " <<nxt<< endl;
}
#undef int
return prev;
}
