#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
int LocateCentre(int N, int P[], int S[], int D[]) {
vector<vector<int>> edges(N);
for (int i = 0; i < N - 1; ++i) {
edges[S[i]].push_back(D[i]);
edges[D[i]].push_back(S[i]);
}
vector<int> sub(N, 0);
int tot = 0;
function<void(int, int)> dfs1 = [&] (int node, int par) {
for (int next : edges[node]) {
if (next == par) continue;
dfs1(next, node);
sub[node] += sub[next];
}
sub[node] += P[node];
tot += P[node];
};
dfs1(0, 0);
int ans = 0, root = 0;
for (int ch : edges[0]) {
ans = max(ans, sub[ch]);
}
function<void(int, int)> dfs2 = [&] (int node, int par) -> void {
int mx = tot - sub[node];
for (int next : edges[node]) {
if (next == par) continue;
mx = max(mx, sub[next]);
}
if (mx < ans) {
ans = mx;
root = node;
}
for (int next : edges[node]) {
if (next == par) continue;
dfs2(next, node);
}
};
dfs2(0, 0);
return root;
}
