#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int LocateCentre(int N, int pp[], int S[], int D[]) {
ll sm=0;
for(int i=0;i<N;i++)sm+=pp[i];
pair<ll,int> ans={1e15, 0};
vector<vector<int>> al(N);
for(int i=0;i<N-1;i++){
al[S[i]].push_back(D[i]);
al[D[i]].push_back(S[i]);
}
auto dfs=[&](auto && dfs, int x, int p)->ll{
ll mx=0, sub=pp[x];
for(auto it:al[x]){
if(it==p)continue;
ll ret=dfs(dfs, it, x);
mx=max(mx, ret);
sub+=ret;
}
mx=max(mx, sm-sub);
//~ printf("at %d, sub %lld\n", x, sub);
ans=min(ans, {mx, x});
return sub;
};
dfs(dfs, 0, -1);
return ans.second;
}
