#include "traffic.h"
// #define int long long
#include<bits/stdc++.h>
using namespace std;
int sum=0,ans2=INT_MAX;
signed ans1;
int solve(int now,int prev,vector<vector<int>> &path,int pp[]){
int nsum=0;
for(auto x:path[now]){
if(x!=prev)nsum+=(solve(x,now,path,pp));
}
int nmn=max(nsum,sum-nsum);
if(nmn<ans2){
ans1=now;ans2=nmn;
}
return nsum+pp[now];
}
signed LocateCentre(int N, int pp[], int S[], int D[]) {
int freq[N]={0};
vector<vector<int>> path(N);
// for(auto x:path){
// for(auto Y:x){
// cout<<Y<<' ';
// }
// cout<<'\n';
// }
for(int i=0;i<N-1;i++){
freq[S[i]]++;
freq[D[i]]++;
sum+=pp[i];
path[S[i]].push_back(D[i]);
path[D[i]].push_back(S[i]);
}
// for(auto x:path){
// for(auto Y:x){
// cout<<Y<<' ';
// }
// cout<<'\n';
// }
for(int i=0;i<N;i++){
if(freq[i]==1){
solve(i,-1,path,pp);
break;
}
}
return ans1;
}
