#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
vector<bool> seen;
vector<int> p, PP;
vector<vector<int>> g;
int dfs(int cur){
if (seen[cur]) return 0;
seen[cur] = true;
p[cur] += PP[cur];
for (int next : g[cur]) p[cur] += dfs(next);
return p[cur];
}
int LocateCentre(int N, int pp[], int S[], int D[]){
int t = 0;
PP.resize(N);
for (int i=0; i<N; i++){
PP[i] = pp[i];
t += PP[i];
}
g.resize(N);
for (int i=0; i<N; i++){
g[S[i]].push_back(D[i]);
g[D[i]].push_back(S[i]);
}
seen.resize(N, false);
p.resize(N, 0);
dfs(0);
int bsf = t, best = -1;
for (int i=0; i<N; i++){
int worst = t-p[i];
for (int j : g[i]){
if (p[j] < p[i]) worst = max(worst, p[j]);
}
if (worst < bsf){
bsf = worst;
best = i;
}
}
return best;
}
