#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
vector<int> sz;
int total = 0;
vector<int> vec;
int dfs(int node, int prev) {
int mx = 0;
int sum = vec[node];
for (auto next : graph[node]) {
if (next != prev) {
int val = dfs(next, node);
mx = max(mx, val);
sum += val;
}
}
mx = max(total - sum, mx);
sz[node] = mx;
return sum;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
graph.resize(N);
sz.resize(N);
vec.resize(N);
for (int i = 0; i < N; i++) {
vec[i] = pp[i];
total += pp[i];
}
for (int i = 0; i < N - 1; i++) {
graph[S[i]].push_back(D[i]);
graph[D[i]].push_back(S[i]);
}
dfs(0, -1);
int ans = -1;
int num = 2e9 + 2;
for (int i = 0; i < N; i++) {
if (sz[i] < num) {
num = sz[i];
ans = i;
}
}
return ans;
}
