加拿大虽然是一个大国，但许多地区无人居住，大部分人口居住在南部边境附近。横贯加拿大公路（Trans-Canada Highway）于 1962 年完工，连接了居住在这片狭长地带的人们，从东部的圣约翰斯（St. John's）到西部的维多利亚（Victoria），全长 7821 公里。

加拿大人喜欢冰球。一场冰球比赛结束后，成千上万的球迷开车从比赛场地回家，导致道路严重拥堵。一位富有的企业家想要收购一支冰球队并建造一座新的冰球馆。你的任务是帮助他选择一个球馆位置，以最大限度地减少比赛后的交通拥堵。

该国由通过道路网络连接的城市组成。所有道路都是双向的，且任意两个城市之间有且仅有一条路径。连接城市 $c_0$ 和 $c_k$ 的路径是一个由不同城市组成的序列 $c_0, \dots, c_k$，使得对于每个 $i$，都有一条从 $c_{i-1}$ 到 $c_i$ 的道路。新球馆必须建在其中一个城市中，我们称之为“球馆城市”。比赛结束后，所有的冰球球迷都会从球馆城市出发前往他们各自的居住城市，除了那些已经居住在球馆城市的球迷。每条道路上的拥堵程度与沿该道路行驶的冰球球迷数量成正比。你必须确定球馆城市的位置，使得最拥堵道路上的拥堵程度尽可能小。如果有多个同样好的位置，你可以选择其中任何一个。

你需要实现一个过程 LocateCentre(N, P, S, D)。$N$ 是一个正整数，表示城市数量。城市编号从 $0$ 到 $N-1$。$P$ 是一个包含 $N$ 个正整数的数组；对于每个 $i$，$P[i]$ 是居住在编号为 $i$ 的城市中的冰球球迷数量。所有城市中的冰球球迷总数最多为 $2\,000\,000\,000$。$S$ 和 $D$ 是两个包含 $N-1$ 个整数的数组，分别指定了道路的连接情况。对于每个 $i$，有一条连接编号为 $S[i]$ 和 $D[i]$ 的两个城市的道路。该过程必须返回一个整数，即应该作为球馆城市的城市编号。

样例

考虑右侧顶部图示中的五个城市网络，其中城市 0、1 和 2 各包含 10 名冰球球迷，城市 3 和 4 各包含 20 名冰球球迷。中间的图示显示了当新球馆位于城市 2 时的情况，最严重的拥堵为 40（加粗箭头所示）。底部的图示显示了当新球馆位于城市 3 时的情况，最严重的拥堵为 30（加粗箭头所示）。因此，城市 3 是比城市 2 更好的球馆位置。

Figure 1. 考虑右侧顶部图示中的五个城市网络，其中城市 0、1 和 2 各包含 10 名冰球球迷，城市 3 和 4 各包含 20 名冰球球迷。中间的图示显示了当新球馆位于城市 2 时的情况，最严重的拥堵为 40（加粗箭头所示）。底部的图示显示了当新球馆位于城市 3 时的情况，最严重的拥堵为 30（加粗箭头所示）。

说明

我们提醒参赛者，在给定的约束条件下，提交的方案可能通过子任务 3 但未通过子任务 2。然而，请记住，你的最终得分仅由你的其中一次提交决定。

子任务

子任务 1： 假设所有城市都位于从东到西的直线上，且所有道路都沿这条直线延伸，没有分支。更具体地说，假设对于所有 $0 \le i \le N-2$，都有 $S[i] = i$ 且 $D[i] = i+1$。城市数量最多为 1000。

子任务 2： 做出与子任务 1 相同的假设，但城市数量最多为 $1\,000\,000$。

子任务 3： 子任务 1 中的假设可能不再成立。城市数量最多为 1000。

子任务 4： 子任务 1 中的假设可能不再成立。城市数量最多为 $1\,000\,000$。