#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int LocateCentre(int n, int p[], int s[], int d[]) {
vector<vector<int>> G(n);
for (int i = 0; i < n - 1; ++i) {
G[s[i]].emplace_back(d[i]);
G[d[i]].emplace_back(s[i]);
}
vector<ll> dps(n), dpm(n), dpa(n);
function<void(int, int)> dfs = [&](int node, int last) {
dps[node] = p[node];
for (auto x : G[node])
if (x != last) {
dfs(x, node);
dps[node] += dps[x];
dpm[node] = max(dpm[node], dps[x]);
}
};
dfs(0, -1);
dpa[0] = dpm[0];
function<void(int, int)> dfs2 = [&](int node, int last) {
for (auto x : G[node])
if (x != last) {
dpa[x] = max(dpm[x], dps[0] - dps[x]);
dfs2(x, node);
}
};
dfs2(0, -1);
return min_element(dpa.begin(), dpa.end()) - dpa.begin();
}
