#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> sos;
vector<vector<int>> adjlist;
vector<int> sizes;
vector<int> parent;
void dfs(int node, int par) {
int su=0;
for (auto j:adjlist[node]) {
if (j==par) {
continue;
}
parent[j] = node;
dfs(j,node);
su+=sos[j];
}
su+=sizes[node];
sos[node] = su;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
adjlist=vector<vector<int>>(N);
sizes=vector<int>(N);
sos=vector<int>(N,0);
parent=vector<int>(N,-1);
int alls = 0;
for (int i=0; i<N; i++) {
sizes[i] = pp[i];
alls+=sizes[i];
}
for (int i=0; i<N-1; i++) {
adjlist[S[i]].push_back(D[i]);
adjlist[D[i]].push_back(S[i]);
}
dfs(0, -1);
for (int i=0; i<N; i++) {
//cout << i <<" " << parent[i] << endl;
}
int INF=2100000000;
int mans=INF;
int mpos = -1;
for (int i=0; i<N; i++) {
int ma=0;
int tsum=0;
for (auto j:adjlist[i]) {
if (j==parent[i]) {
continue;
}
ma=max(ma,sos[j]);
tsum+=sos[j];
//cout << i <<" " <<j <<" " << sos[j] << endl;
}
tsum+=sizes[i];
tsum=alls-tsum;
ma=max(ma,tsum);
//cout << i <<" " << ma << endl;
if (ma<mans) {
mans=ma;
mpos=i;
}
}
return mpos;
}
