#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using igrid = vector<idata>;
idata weight;
idata subtree_weight;
idata parents;
igrid roads;
int dfs (int node, int parent) {
parents[node] = parent;
subtree_weight[node] = weight[node];
for (int next : roads[node]) if (next != parent)
subtree_weight[node] += dfs(next, node);
return subtree_weight[node];
}
int count (int source, int target) {
if (parents[source] == target)
return subtree_weight[0] - subtree_weight[source];
return subtree_weight[target];
}
int find (int source) {
int res = 0;
for (int u : roads[source])
res = max(res, count(source, u));
return res;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
weight.resize(N);
for (int i = 0; i < N; i ++) weight[i] = pp[i];
roads.resize(N);
parents.resize(N);
subtree_weight.resize(N);
for (int i = 0; i + 1 < N; i ++) {
roads[S[i]].push_back(D[i]);
roads[D[i]].push_back(S[i]);
}
dfs(0, -1);
pair<int, int> H = { 2e9 + 10, 0 };
for (int i = 0; i < N; i ++) {
pair<int, int> local = { find(i), i };
H = min(H, local);
}
return H.second;
}
