#include<traffic.h>
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
using namespace std;
const int N = 1000000 + 5;
const int MOD = 1e9 + 7;
vector<int> graph[N];
long long int dis[N], mx[N], total;
void dfs(int source, int par, int p[]){
for(auto k : graph[source]){
if(k != par){
dfs(k, source, p);
dis[source] += dis[k];
mx[source] = max(mx[source], dis[k]);
}
}
mx[source] = max(mx[source], total - dis[source] - p[source]);
dis[source] += p[source];
}
int LocateCentre(int n, int p[], int S[], int D[]){
for(int i = 0; i < n - 1; ++i){
graph[S[i]].push_back(D[i]);
graph[D[i]].push_back(S[i]);
total += p[i];
}
total += p[n - 1];
dfs(0, -1, p);
long long res = 0, ans = INT_MAX;
for(int i = 0; i < n; ++i){
if(mx[i] < ans){
ans = mx[i];
res = i;
}
}
return res;
}
/*
5
10 10 10 20 20
0 2
1 2
2 3
3 4
*/
