#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
long long getSubTree(int nodo, int P[], int padre, vector<long long>& subtrees, vector<vector<int>>& adj, vector<long long>& maxRoad, long long total){
if(subtrees[nodo]!=-1) return subtrees[nodo];
long long suma = 0;
for(int i=0;i<adj[nodo].size();i++){
if(adj[nodo][i]==padre) continue;
long long subtree = getSubTree(adj[nodo][i], P, nodo, subtrees, adj, maxRoad, total);
suma += subtree;
maxRoad[nodo] = max(maxRoad[nodo],subtree);
}
maxRoad[nodo] = max(maxRoad[nodo],total-suma-P[nodo]);
subtrees[nodo] = suma+P[nodo];
return subtrees[nodo];
}
int LocateCentre(int N, int P[], int S[], int D[]) {
vector<vector<int>> adj(N);
vector<long long> subtree(N,-1);
vector<long long> maxRoad(N,0);
long long suma = 0;
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);
}
for(auto i=0;i<N;i++) suma+=P[i];
getSubTree(0,P,-1,subtree, adj, maxRoad, suma);
long long minRoad = maxRoad[0];
int idx = 0;
//cout<<suma<<endl;
//for(int i=0;i<N;i++) cout<<i<<" "<<maxRoad[i]<<" "<<subtree[i]<<endl;
for(int i=1;i<N;i++){
if(maxRoad[i]<minRoad){
minRoad = maxRoad[i];
idx = i;
}
}
return idx;
}
