#include <bits/stdc++.h>
#define see(x) cerr<<#x<<"="<<x<<"\n";
using namespace std;
vector <int> sum, max_edge, last_edge;
vector <vector <int>> g;
void dfs (int v, int par, int P[]) {
sum[v] = 0;
max_edge[v] = 0;
for (auto i: g[v]) {
if (i != par) {
dfs(i, v, P);
sum[v] += sum[i] + P[i];
max_edge[v] = max(max_edge[v], sum[i] + P[i]);
}
}
}
void dfs_for_last_edge (int v, int par, int P[]) {
for (auto i: g[v]) {
if (i != par) {
last_edge[i] = sum[v] + P[v] + last_edge[v] - sum[i] - P[i];
dfs_for_last_edge(i, v, P);
}
}
}
int LocateCentre (int N, int P[], int S[], int D[]) {
g.resize(N);
sum.resize(N);
max_edge.resize(N);
last_edge.resize(N);
for (int i = 0; i < N - 1; i ++) {
g[S[i]].push_back(D[i]);
g[D[i]].push_back(S[i]);
}
last_edge[0] = 0;
dfs(0, -1, P);
dfs_for_last_edge(0, -1, P);
int min_res = max_edge[0], ans = 0;
for (int i = 1; i < N; i ++) {
int cur = max(max_edge[i], last_edge[i]);
if (cur < min_res) {
min_res = cur;
ans = i;
}
}
return ans;
}
