#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6;
const int maxC = 2e9;
vector<int> arr[maxN];
int fans = 0;
int children[maxN];
int ans[maxN];
int node[maxN];
void dfs(int curr, int parent){
for (int index : arr[curr]){
if (index != parent){
dfs(index, curr);
// add the number of children for my children (subtree)
children[curr] += children[index];
ans[curr] = max(ans[curr], children[index]); // select the grestest subtree
}
}
ans[curr] = max(ans[curr], fans - node[curr] - children[curr]);
children[curr] += node[curr];
}
int LocateCentre(int n, int p[], int s[], int d[]){
for (int i=0; i<n; i++){
fans += p[i];
node[i] = p[i];
}
for (int i=0; i<n-1; i++){
arr[s[i]].push_back(d[i]);
arr[d[i]].push_back(s[i]);
}
// start dfs and find subtree fans
dfs(0, -1);
int out = 0;
int sol = 2e9;
for (int i=0; i<n; i++){
if (ans[i] < sol){
sol = ans[i];
out = i;
}
}
return out;
}
