// #pragma once
#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
int const NN=1e6+5;
int fans[NN];
vector<int> adj[NN];
int sub[NN];
int ans=2000000001;
int arne=0;
void reroot(int a,int b){
sub[a]-=sub[b];
sub[b]+=sub[a];
}
void dfs(int node,int par){
int mx=0;
for(auto i:adj[node])
mx=max(sub[i],mx);
if(mx<ans){
arne=node;
ans=mx;
}
for(auto i:adj[node])
if(i!=par){
reroot(node,i);
dfs(i,node);
reroot(i,node);
}
}
void cal_sub(int node,int par){
for(auto i:adj[node]){
if(i!=par){
cal_sub(i,node);
sub[node]+=sub[i];
}
}
sub[node]+=fans[node];
}
int LocateCentre(int N, int P[], int S[], int D[]){
for (int i = 0; i <N; ++i)
fans[i]=P[i];
for (int i = 0; i < N-1; ++i)
{
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
cal_sub(0,-1);
dfs(0,-1);
return arne;
}
