#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<int> g[1000100];
ll subsum[1000100] = {0};
int ans = 0; ll optimal = numeric_limits<ll>::max();
void dfs(int node, int prev = -1){
for(auto i : g[node]){
if(i != prev){
dfs(i, node);
subsum[node] += subsum[i];
}
}
}
void solve(int node, int prev = -1){
ll maxsubtree = subsum[0] - subsum[node];
for(auto i : g[node]){
if(i != prev){
maxsubtree = max(maxsubtree, subsum[i]);
solve(i, node);
}
}
if(maxsubtree < optimal){
optimal = maxsubtree;
ans = node;
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for(int i = 0; i < N - 1; ++i){
g[S[i]].push_back(D[i]);
g[D[i]].push_back(S[i]);
subsum[i] = pp[i];
}
subsum[N - 1] = pp[N - 1];
dfs(0);
solve(0);
return ans;
}
