#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
vector<vector<int>> adj;
int tot = 0;
int mx = INT_MAX, ans = 0;
int dfs(int cur, int p) {
int sum = 0;
int m = 0;
for (auto e : adj[cur]) {
if (e != p) {
int cnt = dfs(e, cur);
m = max(cnt, m);
sum += cnt;
}
}
m = max(m, tot-a[cur]-sum);
if (m < mx) {
mx = m;
ans = cur;
}
return sum+a[cur];
}
int LocateCentre(int N, int P[], int S[], int D[]) {
adj.resize(N);
a.resize(N);
for (int i = 0; i < N; i++) {
a[i] = P[i];
tot += a[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, 0);
return ans;
}
