#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e6;
const int INF = 1e9 + 5;
int fans;
vector<int> adj[mxN], nodes(mxN), people(mxN), children(mxN);
void dfs(int u, int parent) {
for (int v : adj[u]) {
if (v == parent) continue;
dfs(v, u);
children[u] += children[v];
people[u] = max(people[u], children[v]);
}
people[u] = max(people[u], fans - nodes[u] - children[u]);
children[u] += nodes[u];
}
int LocateCentre(int N, int P[], int S[], int D[]) {
for (int i=0; i < N; i++) {
nodes[i] = P[i];
fans += P[i];
}
for (int i=0; i < N-1; i++) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs(0, -1);
int ans = INF, a1 = 0;
for (int i=0; i < N; i++) {
if (people[i] < ans) {
ans = people[i];
a1 = i;
}
}
return a1;
}
