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