#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
const ll INF = 1e18L;
vector<vector<int>> adj;
ll dfs(int node, int prev, int* pp, vector<ll>& sz) {
sz[node] = pp[node];
for(int x : adj[node]) {
if(x == prev) continue;
sz[node] += dfs(x, node, pp, sz);
}
return sz[node];
}
int LocateCentre(int n, int pp[], int S[], int D[]) {
adj.clear();
adj.resize(n);
for(int i = 0; i + 1 < n; ++i) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
vector<ll> sz(n);
dfs(0, -1, pp, sz);
ll mx = INF;
int node = -1;
for(int i = 0; i < n; ++i) {
// check if this city is the best one
ll local = max(abs(sz[0] - sz[i]), sz[i] - pp[i]);
if(local < mx) {
mx = local;
node = i;
}
}
assert(node != -1);
return node;
}
