#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
vector<int> adj[1000000];
ll sum[1000000];
pair<ll, int> ans = {LLONG_MAX,-1};
ll solve(int x, int p, int pp[], ll t){
ll maxx=0;
sum[x]=pp[x];
for(auto c : adj[x]) if(c!=p){
ll sum1=solve(c,x,pp,t);
maxx=max(maxx,sum1);
sum[x]+=sum1;
}
maxx=max(maxx,t-sum[x]);
ans=min(ans,{maxx,x});
return sum[x];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
ll total=0;
for(int i=0;i<N;i++){
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
total+=pp[i];
}
solve(0,-1,pp,total);
return ans.second;
}
