#include "traffic.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
vector<vector<int>> gra;
vector<int> chi, big, val;
pair<int,int> ans;
int tot = 0;
void dfs(int x, int p){
for(int v : gra[x]){
if(v == p)continue;
dfs(v,x);
chi[x] += chi[v];
big[x] = max(big[x], chi[v]);
}
big[x] = max(big[x], tot-val[x]-chi[x]);
chi[x] += val[x];
}
int LocateCentre(int n, int pp[], int s[], int d[]) {
chi.resize(n,0);
big.resize(n,0);
gra.resize(n);
for(int i = 0; i < n-1; ++i){
gra[s[i]].push_back(d[i]);
gra[d[i]].push_back(s[i]);
}
for(int i = 0; i < n; ++i){
val.push_back(pp[i]);tot+=pp[i];
}
dfs(0,0);
ans = {tot,-1};
for(int i = 0; i < n; ++i){
if(big[i] < ans.f){
ans.f = big[i];
ans.s = i;
}
}
return ans.s;
}
