#include <vector>
#include "traffic.h"
using namespace std;
int const INF = 2e9+1;
int const NMAX = 1e6;
int val[1 + NMAX];
int ans[1 + NMAX];
vector <int> g[1 + NMAX];
int total;
int sub[1 + NMAX];
void DFS(int node, int parent) {
ans[node] = 0;
sub[node] = val[node];
for(int i = 0;i < g[node].size();i++) {
int to = g[node][i];
if(to != parent) {
DFS(to, node);
ans[node] = max(ans[node], sub[to]);
sub[node] += sub[to];
}
}
ans[node] = max(ans[node], total - sub[node]);
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
int n;
n = N;
for(int i = 1;i <= n;i++) {
val[i] = pp[i-1];
total += val[i];
}
for(int i = 1;i < n;i++) {
int a, b;
a = S[i-1] + 1;
b = D[i-1] + 1;
g[a].push_back(b);
g[b].push_back(a);
}
DFS(1, 1);
int sol = INF, best = 0;
for(int i = 1;i <= n;i++) {
if(ans[i] < sol) {
best = i;
sol = ans[i];
}
}
return (best-1);
}
