#include "traffic.h"
#include <bits/stdc++.h>
const int mx = 1e6;
int fans;
std::vector <int> adj[mx];
std::vector <int> children(mx),ppl(mx),nodes(mx);
void dfs(int node,int parent){
for (auto x : adj[node]){
if (x == parent) continue;
dfs(x,node);
children[node] += children[x];
ppl[node] = std::max(ppl[node],children[x]);
}
ppl[node] = std::max(ppl[node],fans-children[node]-nodes[node]);
children[node] += nodes[node];
}
int LocateCentre(int n,int p[],int s[],int d[]){
for (int i = 0 ; i < n ; i++){
fans += p[i];
nodes[i] = p[i];
}
for (int i = 0 ; i < n-1 ; i++){
adj[d[i]].push_back(s[i]);
adj[s[i]].push_back(d[i]);
}
dfs(0,-1);
int ans = INT_MAX;
int res = -1;
for (int i = 0 ; i < n ; i++){
if (ppl[i] < ans)
{
ans = ppl[i];
res = i;
}
}
return res;
}
