// 6 tries for such an easy prob 😭
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first
// #define S second
#include "traffic.h"
int N;
vector<int> P;
int tot, mn = INT_MAX, res = -1;
vector<vector<int>> adj;
int dfs(int n, int p) {
int subsum = 0;
int submax = 0;
for(auto c: adj[n]) {
if (c != p) {
int s = dfs(c, n);
submax = max(submax, s);
subsum += s;
}
}
if (mn > max(submax, tot - subsum - P[n])) {
mn = max(submax, tot - subsum - P[n]);
res = n;
}
return subsum + P[n];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
::N = N;
adj.resize(N);
P.resize(N);
FOR(i, N) P[i] = pp[i];
tot = accumulate(all(P), 0);
FOR(i, N-1) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs(0,0);
return res;
}
// signed main() {
// cin.tie(0); ios::sync_with_stdio(false);
// }
