#include <iostream>
#include <vector>
#include "traffic.h"
using namespace std;
typedef long long ll;
ll ans=1e18;
int node=-1;
ll dfs(int a,vector<vector<int> >& v,int par,ll tot,vector<int>& w){
ll sol=0,parw=0;
for(int x:v[a]){
if(x!=par){
ll af=max(dfs(x,v,a,tot,w),sol);
sol=max(sol,af);
parw+=af;
}
}
ll fin=max(sol,tot-parw-w[a]);
if(fin<ans){
ans=fin;
node=a;
}
return parw+w[a];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
vector<vector<int> > v(N,vector<int>());
vector<int> w(N);
ll tot=0;
for(int i=0;i<N;i++)w[i]=pp[i];
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++)tot+=pp[i];
dfs(0,v,-1,tot,w);
return node;
}
/*int main(){
int n;
cin>>n;
int pp[n],s[n],d[n];
for(int i=0;i<n;i++)cin>>pp[i];
for(int i=0;i<n-1;i++)cin>>s[i]>>d[i];
cout<<LocateCentre(n,pp,s,d);
}*/
