CF1436D Bandit in a City

城市里出现了强盗！其中一名强盗试图抓住尽可能多的市民。 这座城市由 $n$ 个广场组成，通过 $n-1$ 条道路连接，使得从任意一个广场都可以到达其他任意一个广场。编号为 $1$ 的广场是主广场。 在周日散步之后，所有道路都变成了单向道路，方式是从主广场可以到达任意一个广场。 当强盗出现在主广场时，第 $i$ 个广场上有 $a_i$ 名市民。现在将开始如下过程：首先，每个当前位于有出边的广场上的市民会选择一条出边，沿着这条单向路移动到另一个广场。然后，强盗选择一条他所在广场的出边，沿着这条单向路移动。该过程不断重复，直到强盗到达一个没有出边的广场为止。强盗会抓住该广场上的所有市民。 强盗希望抓住尽可能多的市民，而市民们希望被抓住的人数最少。强盗和市民都随时知道所有市民的位置，且市民们可以合作。如果双方都采取最优策略，强盗最终能抓住多少市民？

第一行包含一个整数 $n$，表示城市中广场的数量（$2 \le n \le 2 \cdot 10^5$）。 第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$，表示存在一条从广场 $p_i$ 到广场 $i$ 的单向道路（$1 \le p_i < i$）。 第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个广场初始时的市民数量（$0 \le a_i \le 10^9$）。

输出一个整数，表示如果双方都采取最优策略，强盗最终能抓住的市民数量。

在第一个样例中，主广场上的市民可以分成 $2+1$ 两组，使得第 $2$ 个和第 $3$ 个广场上各有 $3$ 名市民。 在第二个样例中，无论市民如何行动，强盗都至少能抓住 $4$ 名市民。 由 ChatGPT 4.1 翻译