#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
const int MAX_N = 1e6 + 10;
const int INF = 2e9 + 7;
int P[MAX_N], sum[MAX_N], max_congestion = INF, ans;
vector <int> graph[MAX_N];
int dfs(const int &u, const int &p) {
sum[u] = P[u];
for(auto v : graph[u]) {
if(v != p) {
sum[u] += dfs(v, u);
}
}
return sum[u];
}
void dfs2(const int &u, const int &p, const int &ps) {
int ma = ps;
for(auto v : graph[u]) {
if(v == p) {
continue;
}
ma = max(ma, sum[v]);
dfs2(v, u, sum[u] + ps - sum[v]);
}
if(max_congestion > ma) {
max_congestion = ma;
ans = u;
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for(int i = 1; i <= N; i++) {
P[i] = pp[i - 1];
}
for(int i = 0; i < N - 1; i++) {
S[i]++, D[i]++;
graph[S[i]].push_back(D[i]);
graph[D[i]].push_back(S[i]);
}
dfs(1, -1);
dfs2(1, -1, 0);
return ans - 1;
}
