#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
template <class T> using v = vector<T>;
using ll = long long;
ll sum = 0;
v<ll> sums;
v<v<int>> adj;
pair<ll, int> ans = {LLONG_MAX, -1};
void dfs(int node, int par) {
ll cur = 0;
for (auto next : adj[node]) {
if (next != par) {
dfs(next, node);
sums[node] += sums[next];
cur = max(cur, sums[next]);
}
}
cur = max(cur, sum - sums[node]);
ans = min(ans, {cur, node});
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
adj.resize(N);
sums.resize(N);
for (int i = 0; i < N; i++) {
sum += pp[i];
sums[i] = pp[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);
return ans.second;
}
