#include "traffic.h"
#include <vector>
using namespace std;
#define pb push_back
#define oo 1000000000
vector<vector<int>> ed;
vector<int> subtr;
vector<int> res;
int sum = 0;
void calcSubtreeSum(int v, int pr){
for (auto to : ed[v]){
if (to == pr) continue;
calcSubtreeSum(to, v);
subtr[v] += subtr[to];
}
}
void dfs(int v, int pr){
if (pr != -1) res[v] = sum - subtr[v];
for (auto to : ed[v]){
if (to == pr) continue;
res[v] = max(res[v], subtr[to]);
dfs(to, v);
}
}
int LocateCentre(int n, int pp[], int s[], int d[]) {
ed.resize(n);
subtr.resize(n);
res.resize(n);
for (int i = 0; i < n; ++i) {
subtr[i] += pp[i];
sum += pp[i];
}
for (int i = 0; i < n-1; ++i){
ed[s[i]].pb(d[i]);
ed[d[i]].pb(s[i]);
}
calcSubtreeSum(0, -1);
dfs(0, -1);
int mn = oo * 2;
int ans = 0;
for (int i = 0; i < n; ++i) {
if (res[i] < mn) mn = res[i], ans = i;
}
return ans;
}
