#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 10;
ll cnt[MAXN], sub[MAXN];
ll dp_1[MAXN], dp_2[MAXN];
vector<int> adj[MAXN];
void dfs_1(int v, int p){
dp_1[v] = 0;
sub[v] = cnt[v];
for(auto u : adj[v]){
if(u != p){
dfs_1(u, v);
sub[v] += sub[u];
dp_1[v] = max({dp_1[v], dp_1[u], sub[u]});
}
}
}
void dfs_2(int v, int p){
ll cur_max = 0;
for(auto u : adj[v]){
if(u != p){
dp_2[u] = max({dp_2[v], sub[1] - sub[u], cur_max});
cur_max = max({cur_max, dp_1[u], sub[u]});
}
}
reverse(adj[v].begin(), adj[v].end());
cur_max = 0;
for(auto u : adj[v]){
if(u != p){
dp_2[u] = max(dp_2[u], cur_max);
cur_max = max({cur_max, dp_1[u], sub[u]});
}
}
for(auto u : adj[v]) if(u != p) dfs_2(u, v);
}
int LocateCentre(int n, int p[], int s[], int d[]){
for(int i=1; i<=n; i++) adj[i].clear();
for(int i=0; i<n; i++) cnt[i + 1] = p[i];
for(int i=0; i<(n - 1); i++){
adj[s[i] + 1].push_back(d[i] + 1);
adj[d[i] + 1].push_back(s[i] + 1);
}
dfs_1(1, 1);
dp_2[1] = 0;
dfs_2(1, 1);
pair<ll, int> ans = {dp_1[1], 1};
for(int i=2; i<=n; i++) ans = min(ans, {max(dp_1[i], dp_2[i]), i});
return ans.second - 1;
}
