#include <bits/stdc++.h>
using namespace std;
void dfs(int head, int par, vector<int> &maxi, vector<int> &total, vector<vector<int>> &tree, int s){
for(int i : tree[head]){
if(i != par){
dfs(i, head, maxi, total, tree, s);
total[head] += total[i];
maxi[head] = max(maxi[head], total[i]);
}
}
maxi[head] = max(maxi[head], s - total[head]);
}
int LocateCentre(int N, int P[], int S[], int D[]){
vector<vector<int>> tree(N);
for(int i = 0; i < N-1; i ++){
tree[S[i]].push_back(D[i]);
tree[D[i]].push_back(S[i]);
}
vector<int> maxi(N), total(N);
int s = 0;
for(int i = 0; i < N; i ++){
total[i] = P[i];
s += P[i];
}
dfs(0, -1, maxi, total, tree, s);
int ans = 2e9, id = -1;
for(int i = 0; i < N; i ++){
if(ans > maxi[i]){
ans = maxi[i];
id = i;
}
}
return id;
}
