#include "traffic.h"
#include <vector>
#include <utility>
#include <climits>
#include <iostream>
std::vector<int> adj[1000005];
long long tot, sz[1000005];
std::pair<long long, int> ans = {LLONG_MAX, -1};
long long dfs(int x, int pp[], int p=-1) {
sz[x] = pp[x];
long long cmax = 0;
for(auto &e:adj[x]) {
if(e == p) continue;
cmax = std::max(cmax, dfs(e, pp, x));
sz[x] += sz[e];
}
cmax = std::max(cmax, tot - sz[x]);
ans = std::min(ans, {cmax, x});
//std::cout << cmax << ' ' << x << '\n';
return sz[x];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
tot = pp[N-1];
for(int i=0;i<N-1;i++) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
tot += pp[i];
}
dfs(0, pp);
return ans.second;
}
