#include <bits/stdc++.h>
using namespace std;
#include "traffic.h"
vector<vector<int>>adj;
int n;
vector<int>v;
vector<int>mx,total;
int root_dfs(int u, int e = -1) {
int w = v[u];
for(auto z : adj[u]) {
if(z == e) continue;
int curr = root_dfs(z,u);
w+=curr;
mx[u] = max(mx[u],curr);
}
return total[u] = w;
}
int best, mn = INT_MAX;
void dfs(int u, int sum, int e = -1) {
if(max(mx[u],sum) < mn) {
mn = max(mx[u],sum);
best = u;
}
for(auto z : adj[u]) {
if(z == e) continue;
int nw = total[u] - total[z] + sum;
dfs(z,nw,u);
}
}
int LocateCentre(int nn, int p[], int s[], int d[]) {
n=nn;
adj.resize(n);
v.resize(n);
for(int i = 0 ; i < n ; i++) v[i] = p[i];
mx.resize(n,0);
total.resize(n,0);
for(int i = 0 ; i < n-1 ; i++) {
adj[s[i]].push_back(d[i]);
adj[d[i]].push_back(s[i]);
}
root_dfs(0);
dfs(0,0);
return best;
}
