← 返回题目列表

Codeforces · 1436/D

D. 城市里的强盗

中文机器翻译题面 查看原题

城里出现强盗!其中一人正试图抓住尽可能多的公民。

该城市由 $$$n$$$ 广场组成,通过 $$$n-1$$$ 道路连接,可以从任何其他广场到达任何广场。方格数字 $$$1$$$ 是主方格。

周日步行之后,所有道路都改为单向道路,这样就可以从主广场到达任何广场。

当强盗出现在主广场上时,第​​$$$i$$$个广场上有$$$a_i$$$公民。现在将开始以下过程。首先,当前位于具有一些向外单向道路的广场上的每个公民选择其中一条道路并沿着它移动到另一个广场。然后强盗选择从他所在的广场出发的单向道路之一并沿着它移动。重复该过程,直到强盗位于没有出口道路的广场上。强盗抓住了广场上所有的居民。

强盗想要抓住尽可能多的公民;公民希望尽量减少被捕人数。强盗和公民随时了解所有公民的位置,公民可以合作。如果双方都采取最佳行动,会有多少公民被抓?

输入

第一行包含一个整数 $$$n$$$ — 城市中的方格数 ($$$2 \le n \le 2\cdot10^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$$$)。

输出

打印一个整数——如果双方都采取最佳行动,强盗将捕获的公民数量。

示例

输入 #1

3
1 1
3 1 2

输出 #1

3

输入 #2

3
1 1
3 1 3

输出 #2

4

注意

在第一个示例中,$$$1$$$ 广场上的公民可以分为两组 $$$2 + 1$$$,这样第二个和第三个广场上的每个公民将有 $$$3$$$ 公民。

在第二个例子中,无论公民如何行动,强盗都可以捕获至少 $$$4$$$ 公民。