#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> st;
vector<vector<int>> graph;
vector<bool> visited;
vector<int> parent;
long long preprocess(int curr, int pp[]){
visited[curr] = true;
vector<int> adj = graph[curr];
st[curr] = pp[curr];
for(int a : adj){
if(visited[a]) continue;
parent[a] = curr;
st[curr] += preprocess(a, pp);
}
return st[curr];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
visited.assign(N, 0);
parent.assign(N, 0);
st.assign(N, 0LL);
graph.assign(N, vector<int>());
for(int i = 0; i < N-1; i++){
graph[S[i]].push_back(D[i]);
graph[D[i]].push_back(S[i]);
}
preprocess(0, pp);
// for(int i = 0; i < N; i++) cout<<"DEBUG-->"<<st[i]<<endl;
long long mn = LLONG_MAX;
int ans = -1;
for(int i = 0; i < N; i++){
vector<int> adj = graph[i];
long long mx = -1;
for(int a : adj){
if(a != parent[i]){
if(st[a] > mx) mx = st[a];
}else {
// calcolo della congestione della strada che collega
// i al parent
long long cong = st[0] - st[i];
// cout<<i<<" "<<a<<" "<<cong<<endl;
if(cong > mx) mx = cong;
}
}
if(mx < mn)
ans = i;
mn = min(mn, mx);
}
return ans;
}
