#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1'000'005;
vector<int> adj[maxn];
unordered_map<ll, int> sz;
int a[maxn]; ll n;
inline int dfs(int es, int en) {
const ll ind = es*n+en;
if (sz.count(ind))
return sz[ind];
int s = a[en];
for (const int &j: adj[en])
if (j != es) s += dfs(en, j);
return sz[ind] = s;
}
int LocateCentre(int N, int* P, int* S, int* D) {
n = N;
for (int i = 0; i < n; ++i)
a[i] = P[i];
for (int i = 0; i < n-1; ++i) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
int mn = 2e9, mi = -1;
for (int i = 0, c = 0; i < n; ++i, c = 0) {
for (const int &j: adj[i])
c = max(c, dfs(i, j));
if (c < mn) mn = c, mi = i;
} return mi;
}
