#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>adj;
vector<int>p,maxi,st;
int t=0;
void dfs(int u,int parent){
st[u]+=p[u];
for(int v: adj[u]){
if(v!=parent){
dfs(v,u);
st[u]+=st[v];
maxi[u]=max(maxi[u],st[v]);
}
}
maxi[u]=max(maxi[u],t-st[u]);
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
adj.resize(N);
for(int i=0;i<N-1;i++){
int a=S[i]; int b= D[i];
adj[a].push_back(b);
adj[b].push_back(a);
}
p.resize(N);
maxi.assign(N,0);
st.assign(N,0);
for(int i=0;i<N;i++){
p[i]=pp[i];
t+=p[i];
}
dfs(0,-1);
int mini=2e9+5,ans;
for(int i=0;i<N;i++){
if(mini>maxi[i]){
mini=maxi[i];
ans=i;
}
}
return ans;
}
