#include "traffic.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <array>
using namespace std;
vector<vector<int> > adj;
vector<int> dp;
array<int, 2> ans;
vector<int> cnt;
void dfs(int u, int p) {
dp[u] = cnt[u];
for (int v : adj[u]) {
if (v != p) {
dfs(v, u);
dp[u] += dp[v];
}
}
}
void dfs2(int u, int p) {
int cur = 0;
for (int v : adj[u]) {
cur = max(cur, dp[v]);
}
if (cur < ans[1]) {
ans = {u, cur};
}
for (int v : adj[u]) {
if (v == p) continue;
dp[u] -= dp[v];
dp[v] += dp[u];
dfs2(v, u);
dp[v] -= dp[u];
dp[u] += dp[v];
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
cnt.resize(N);
for (int i = 0; i < N; ++i) {
cnt[i] = pp[i];
}
dp.resize(N);
adj.resize(N);
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);
ans = {0, 0};
for (int v : adj[0]) {
ans[1] = max(ans[1], dp[v]);
}
dfs2(0, -1);
return ans[0];
}
