#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int sz = 1e6+6;
vector<int> g[sz];
vector<int> sub(sz);
int s = 0;
int mn = 2e9+5;
int city;
void dfs(int node, int p){
int mx = 0;
for(auto i: g[node]){
if(i!=p){
dfs(i, node);
}sub[node] += sub[i];
mx = max(mx, sub[i]);
}
mx=max(mx, s-sub[node]);
if(mn > mx){
mx=mx;
city=node;
}
}
int LocateCentre(int n, int P[], 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++){
s += P[i];
sub[i] = P[i];
}dfs(0, -1);
return city;
}
