#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
#define ll long long
const int maxN = 1e6;
vector<int> adj[maxN];
int congestion[maxN];
int children[maxN];
int total;
// use DP on trees to calculate the max into congestion[curr]
// count number of children ONLY AFTER postorder DFS
void DFS(int P[], int curr, int parent) {
for (int child : adj[curr]) {
if (child != parent) {
DFS(P, child, curr);
// add all that child branches counts here
children[curr] += children[child];
// consider how much congestion total on that child branch
congestion[curr] = max(congestion[curr], children[child]);
}
}
// count itself in its children value
children[curr] += P[curr];
// here, consider if we treated this node as the arena
// at this point, we've already considered all the children branches while postorder DFS'ing
// now we consider the congestion of the singular parent branch which was passed over
congestion[curr] = max(congestion[curr], total - children[curr]);
}
int LocateCentre(int N, int P[], int S[], int D[]) {
ll minCongestion = 2e9;
int ans = -1;
total = accumulate(P, P + N, 0);
for (int i = 0; i < N - 1; i++) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
// treat the tree rooted at node 0 and DFS
DFS(P, 0, -1);
// smooth sailing: just pick the arena with the smallest congestion congestion calculated by DFS
for (int i = 0; i < N; i++) {
if (congestion[i] < minCongestion) {
minCongestion = congestion[i];
ans = i;
}
}
return ans;
}
