#ifndef LOCAL
#include "traffic.h"
#endif
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
vector<int> tmp;
void dfs1(int n, int p){
for (auto go : graph[n]){
if (go == p)
continue;
dfs1(go, n);
tmp[n] += tmp[go];
}
}
pair<long long int, int> dfs2(int n, int p, long long int p2=0){
long long int mx = 0;
int j = -1;
for (auto go : graph[n]){
if (go == p)
continue;
if (tmp[go] > mx){
mx = tmp[go];
j = go;
}
}
if (p2 >= mx){
return { p2, n };
}else{
auto u = dfs2(j, n, p2 + tmp[n] - tmp[j]);
if (u.first >= mx){
return { mx, n };
}else{
return u;
}
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
graph.resize(N);
tmp.resize(N);
for (int i = 0; i < N - 1; i++){
graph[S[i]].push_back(D[i]);
graph[D[i]].push_back(S[i]);
}
for (int i = 0; i < N; i++)
tmp[i] += pp[i];
dfs1(0, 0);
return dfs2(0, 0, 0).second;
}
