#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
int n, sum;
int a[1010101];
int sz[1010101];
vector<int> g[1010101];
int cst[1010101];
int ans = -1;
void dfs(int v, int p = -1){
sz[v] = a[v];
for(auto i : g[v]) if(i ^ p){
dfs(i, v); sz[v] += sz[i];
}
}
void solve(int v, int p = -1){
cst[v] = sum - sz[v];
for(auto i : g[v]) if(i ^ p){
cst[v] = max(cst[v], sz[i]);
solve(i, v);
}
if(ans == -1 || cst[ans] > cst[v]) ans = v;
}
int LocateCentre(int N, int P[], int S[], int D[]){
n = N;
for(int i=1; i<=n; i++) a[i] = P[i-1], sum += a[i];
for(int i=0; i<n-1; i++){
int s = S[i] + 1, e = D[i] + 1;
g[s].push_back(e); g[e].push_back(s);
}
dfs(1, -1); solve(1, -1);
return ans - 1;
}
