#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
int LocateCentre(int N, int P[], int S[], int D[]) {
vector<vector<int>> adj(N);
for(int i=0;i<N-1;i++){
int u = S[i];
int v = D[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<long long> maxRoad(N,0);
vector<long long> lastRoad(N,0);
vector<int> visited(N,false);
vector<int> lastNode(N,0);
deque<int> order;
long long sum = 0;
int idx = 0;
for(int i=0;i<N;i++){
if(adj[i].size()>1){
idx = i;
break;
}
}
order.push_front(idx);
while(!order.empty()){
int node = order.front();
if(!visited[node]) sum+=P[node];
visited[node] = true;
//cout<<"SUM: "<<sum<<" NODE: "<<node<<endl;
//cout<<lastNode[node]<<" "<<adj[node].size()<<endl;
bool validNode = false;
for(int i=0;i<adj[node].size();i++){
int newNode = adj[node][i];
//cout<<"NEW NODE: "<<newNode<<endl;
if(adj[newNode].size()==1){
maxRoad[newNode] = max(maxRoad[newNode], sum-lastRoad[newNode] - P[node]);
}else{
maxRoad[newNode] = max(maxRoad[newNode], sum-lastRoad[newNode]);
}
if(!visited[newNode]){
order.push_front(newNode);
lastNode[node]++;
validNode = true;
break;
}
}
if(!validNode) order.pop_front();
else lastRoad[node] = sum;
}
//for(int i=0;i<N;i++) cout<<i<<" "<<maxRoad[i]<<endl;
long long minRoad = maxRoad[0];
idx = 0;
for(int i=0;i<N;i++){
if(maxRoad[i]<minRoad){
minRoad = maxRoad[i];
idx = i;
}
}
return idx;
}
