#include "traffic.h"
#include <vector>
using namespace std;
using ll = long long;
vector<long long> sub(1000001),parent(1000001);
vector<vector<int>> graph(1000001);
vector<long long> arr(1000001);
ll sum=0;
ll mn=4e18,idx=-1;
void dfs(int u,int p){
ll ans=0;
for (int v:graph[u]){
if (v == p) continue;
dfs(v,u);
sub[u] += sub[v]+arr[v];
ans=max(ans,sub[v]+arr[v]);
}
ll re = sum-sub[u]-arr[u];
ans = max(ans,re);
if (mn >= ans){
mn = ans;
idx = u;
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for (int i=0;i<N;i++){
arr[i]=pp[i];
sum+=pp[i];
}
for (int i=0;i<N-1;i++){
graph[S[i]].push_back(D[i]);
graph[D[i]].push_back(S[i]);
}
dfs(0,-1);
return idx;
}
