#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "traffic.h"
vector<ll> nums; vector<vector<int>> adj;
ll mn = 1e18;
ll ans = -1;
ll sm = 0;
void dfs(int u, int p=-1){
ll msz = -1;
for(auto& v:adj[u]){
if (v != p){
dfs(v,u);
nums[u] += nums[v];
msz = max(msz,nums[v]);
}
}
msz = max(msz,sm-nums[u]);
if (msz < mn){
mn = msz; ans = u;
}
}
int LocateCentre(int n, int p[], int s[], int d[]) {
nums.resize(n); adj.resize(n);
for(int i=0;i<n;++i){ nums[i] = p[i]; sm += nums[i];}
for(int i=0;i<n-1;++i) {
adj[s[i]].push_back(d[i]);
adj[d[i]].push_back(s[i]);
}
dfs(0);
return ans;
}
/*
static int N,P[1000000],S[1000000],D[1000000];
int main(){
int i;
scanf("%d",&N);
for (i=0;i<N;i++) scanf("%d",&P[i]);
for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
int r = LocateCentre(N,P,S,D);
printf("%d\n",r);
return 0;
}*/
