#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e6+5;
int ans=2e9, tot, sz[MXN], ver=0;
vector<int> g[MXN];
void dfs(int v, int p=-1) {
int mx = 0;
for(int u : g[v])
if(u!=p) {
dfs(u, v);
sz[v] += sz[u];
mx = max(mx, sz[u]);
}
if(p!=-1) mx = max(mx, tot-sz[v]);
if(mx<ans) {
ans = mx;
ver = v;
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for(int i=0; i<N-1; i++) g[S[i]].push_back(D[i]), g[D[i]].push_back(S[i]);
for(int i=0; i<N; i++) tot += pp[i], sz[i] = pp[i];
dfs(0);
return ver;
}
