#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T>
using vec = vector<T>;
using vll = vec<ll>;
using vvll = vec<vll>;
#define pb push_back
ll n, sum;
vll subtree_size;
vll ans;
vvll adj;
void dfs(ll u, ll p) {
ll mx = -1;
for(ll &v : adj[u]) {
if(v==p) continue;
dfs(v,u);
subtree_size[u] += subtree_size[v];
mx = max(mx, subtree_size[v]);
}
if(p != -1) {
// also check the back edge
mx = max(mx, sum - subtree_size[u]);
}
ans[u] = mx;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
n = N;
subtree_size.assign(n,0ll);
ans.assign(n,1e18);
for(int i = 0; i < n; i++) {
subtree_size[i] = pp[i];
sum += pp[i];
}
adj.resize(n);
for(int i = 0; i < n-1; i++) {
ll u = S[i], v = D[i];
adj[u].pb(v);
adj[v].pb(u);
}
dfs(0,-1);
pair<ll,ll> mn = {1e18,-1};
for(int i = 0; i < n; i++) {
mn = min(mn, {ans[i],i});
}
return mn.second;
}
