#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const long long INF = 1e18;
vector<int> g[maxn];
long long sz[maxn], mx[maxn];
int dfs(int x, int p, long long tot){
int re = -1;
mx[x] = 0;
for(auto v: g[x]){
if(v == p)continue;
int tmp = dfs(v, x, tot);
sz[x] += sz[v];
mx[x] = max(mx[x], sz[v]);
if(re == -1 || mx[tmp] < mx[re])re = tmp;
}
mx[x] = max(mx[x], tot - sz[x]);
if(re == -1 || mx[x] < mx[re])re = x;
return re;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
long long sum = 0;
for(int i = 0; i < N; i++){
g[i].clear();
sz[i] = pp[i];
sum += pp[i];
}
for(int i = 0; i < N-1; i++){
g[S[i]].push_back(D[i]);
g[D[i]].push_back(S[i]);
}
return dfs(0, -1, sum);
}
