#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int MX = (int)(1e6+3);
const int INF = (int)(2e9+1);
typedef pair<int,int> ii;
vector<ii> vec[MX];
int val[MX];
int solve(int node,int p){
int sum=val[node];
for(auto &it:vec[node]){
if(it.fi==p)continue;
if(it.se==-1)
it.se=solve(it.fi,node);
sum+=it.se;
}
return sum;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for (int i = 0; i < N-1; ++i)
{
val[i]=pp[i];
vec[S[i]].push_back({D[i],-1});
vec[D[i]].push_back({S[i],-1});
}
val[N-1]=pp[N-1];
int ans=INF,idx=-1;
for (int i = 0; i < N; ++i)
{
int maxi=0;
for(auto &it:vec[i]){
if(it.se==-1)
it.se=solve(it.fi,i);
maxi=max(maxi,it.se);
}
if(maxi<ans)ans=maxi,idx=i;
}
assert(idx!=-1);
return idx;
}
