#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> adj;
vector <int> st_sz;
vector <int> depth;
int ans = 0;
void dfs(int s, int p, int d) {
depth[s] = d;
for (auto i : adj[s]) {
if (i == p)
continue;
dfs(i, s, d+1);
st_sz[s] += st_sz[i];
if (s == 1)
ans = max(ans, st_sz[i]);
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
adj.resize(N+1);
depth = st_sz = vector <int> (N+1);
for (int i = 0; i < N-1; i++) {
S[i]++;
D[i]++;
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
for (int i = 1; i <= N; i++)
st_sz[i] = pp[i-1];
dfs(1, 1, 0);
int node = 1;
for (int i = 2; i <= N; i++) {
int tp = 0;
for (auto j : adj[i]) {
if (depth[j] > depth[i])
tp = max(tp, st_sz[j]);
else
tp = max(tp, st_sz[1] - st_sz[i]);
}
if (ans > tp) {
ans = tp;
node = i;
}
}
return node-1;
}
// int main() {
// int n;
// int pp[n], s[n], d[n];
// cin >> n;
// for (int i = 0; i < n; i++)
// cin >> pp[i];
// for (int i = 0; i < n-1; i++)
// cin >> s[i] >> d[i];
// cout << LocateCentre(n, pp, s, d) << '\n';
// }
