#include<bits/stdc++.h>
#include "traffic.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 1e6 + 15;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
#define pb push_back
#define sz(x) (int) x.size()
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(), x.end()
int fans = 0;
vector<int> adj[MAX], child(MAX), cong(MAX), fan(MAX);
//child keeps number of children, cong worst congestion, fan number of fans in ith city
void dfs(int x, int p){
for(auto v : adj[x]){
if(v == p) continue;
dfs(v, x);
child[x] += child[v];
cong[x] = max(cong[x], child[v]); //maximum congestion
}
cong[x] = max(cong[x], fans - cong[x] - fan[x]); //worst between children and others (that come through parent)
child[x] += fan[x]; //add to children for next node processing
}
int LocateCentre(int n, int p[], int s[], int d[]){
for(int i = 0; i < n; i++){
fans += p[i];
fan[i] = p[i];
}
for(int i = 0; i < n - 1; i++){
adj[s[i]].pb(d[i]);
adj[d[i]].pb(s[i]);
}
dfs(0, -1);
int id, sm = INF;
for(int i = 0; i < n; i++){ //want city with best worst congestion
if(sm > cong[i]){
id = i, sm = cong[i];
}
}
return id;
}
/*int main(){
setIO();
int P[] = {10, 10, 10, 20, 20};
int S[] = {0, 1, 3, 4};
int D[] = {2, 2, 2, 3};
cout << LocateCentre(5, P, S, D) << '\n';
return 0;
}*/
