#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
vector<long long> subtree(N), c(N);
vector<int> v[N];
long long ans = LLONG_MAX, sum = 0;
int pas;
void dfs1(int u, int par){
subtree[u] = c[u];
for(auto x : v[u]){
if(x == par) continue;
dfs1(x, u);
subtree[u] += subtree[x];
}
}
void dfs2(int u, int par){
long long mx = 0;
mx = max(mx, sum - subtree[u]);
for(auto x : v[u]){
if(x != par){
mx = max(mx, subtree[x]);
dfs2(x, u);
}
}
if(mx < ans){
ans = mx;
pas = u;
}
}
int LocateCentre(int n, int p[], int s[], int d[]){
for(int i = 0; i < n; i++){
c[i] = p[i];
sum += p[i];
if(i == n - 1) continue;
v[s[i]].push_back(d[i]);
v[d[i]].push_back(s[i]);
}
dfs1(0, -1);
dfs2(0, -1);
return pas;
}
