#include "traffic.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e6 + 6;
vector<int> g[MAX];
int arr[MAX];
ll sub[MAX];
void dfs1(int node, int p){
sub[node] = arr[node];
for(int to:g[node]){
if(to == p) continue;
dfs1(to, node);
sub[node] += sub[to];
}
}
ll ans[MAX];
void dfs2(int node, int p){
ans[node] = max(ans[node], sub[0] - sub[node]);
for(int to:g[node]){
if(to == p) continue;
dfs2(to, node);
ans[node] = max(ans[node], sub[to]);
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for (int i = 0; i < N; i++)
{
arr[i] = pp[i];
}
for (int i = 0; i < N - 1; i++)
{
g[S[i]].emplace_back(D[i]);
g[D[i]].emplace_back(S[i]);
}
dfs1(0, 0);
dfs2(0, 0);
int a = 0;
for (int i = 0; i < N; i++)
{
if(ans[i] <= ans[a]){
a = i;
}
}
return a;
}
