#include "traffic.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1000001;
vector<int> adj[N];
ll sz[N];
ll subSz[N];
void dfs1(int node, int par)
{
subSz[node] = sz[node];
for (int next : adj[node])
{
if (next == par) continue;
dfs1(next, node);
subSz[node] += subSz[next];
}
}
array<ll, 2> dfs2(int node, int par)
{
if (par != -1)
{
subSz[par] -= subSz[node];
subSz[node] += subSz[par];
}
array<ll, 2> cur = {0, node};
for (int next : adj[node])
{
cur[0] = max(subSz[next], cur[0]);
}
for (int next : adj[node])
{
if (next == par) continue;
auto ncur = dfs2(next, node);
if (ncur < cur) cur = ncur;
}
subSz[node] -= subSz[par];
subSz[par] += subSz[node];
return cur;
}
int LocateCentre(int n, int p[], int S[], int D[]) {
for (int i = 0; i < n; i++) sz[i] = p[i];
for (int i = 0; i < n - 1; i++)
{
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs1(0, -1);
auto res = dfs2(0, -1);
return res[1];
}
