← 返回题目列表

Codeforces · 1153/D

D. 薮和有根树

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

现在Serval是Japari中学的一名初中生,他仍然像以前一样对数学感到兴奋。

作为一个数学天才男孩,他喜欢玩数字。这一次,他想在一棵有根的树上玩数字。

树是没有循环的连通图。有根树有一个特殊的顶点,称为根。节点 $$$v$$$ 的父节点是从根到顶点 $$$v$$$ 的路径上与 $$$v$$$ 顶点不同的最后一个。顶点 $$$v$$$ 的子节点是以 $$$v$$$ 为父节点的所有节点。如果一个顶点没有子节点,那么它就是一个叶子。

Serval 拥有的根树有 $$$n$$$ 个节点,节点 $$$1$$$ 是根。 Serval 会将一些数字写入树的所有节点。但是,也有一些限制。除叶子节点外,每个节点中都写有一个操作 $$$\max$$$ 或 $$$\min$$$ ,表示该节点中的数字应分别等于其儿子中所有数字的最大值或最小值。

假设树中有 $$$k$$$ 叶子。 Serval 想要将整数 $$$1, 2, \ldots, k$$$ 放入 $$$k$$$ 叶子中(每个数字应该只使用一次)。他喜欢大数字,所以他想最大化根中的数字。作为他最好的朋友,你能帮助他吗?

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 3\cdot 10^5$$$),即树的大小。

第二行包含$$$n$$$个整数,其中第$$$i$$$代表节点$$$i$$$中的操作。 $$$0$$$ 代表$$$\min$$$,$$$1$$$ 代表$$$\max$$$。如果节点是叶子,仍然有一些$$$0$$$或$$$1$$$,但是可以忽略它。

第三行包含 $$$n-1$$$ 整数 $$$f_2, f_3, \ldots, f_n$$$ ($$$1 \leq f_i \leq i-1$$$),其中 $$$f_i$$$ 表示节点 $$$i$$$ 的父节点。

输出

输出一个整数——树根中可能的最大数字。

示例

输入 #1

6
1 0 1 1 0 1
1 2 2 2 2

输出 #1

1

输入 #2

5
1 0 1 0 1
1 1 1 1

输出 #2

4

输入 #3

8
1 0 0 1 0 1 1 0
1 1 2 2 3 3 3

输出 #3

4

输入#4

9
1 1 0 0 1 0 1 0 1
1 1 2 2 3 3 4 4

输出#4

5

注意

下面的图片解释了示例。节点中间写的数字是它们的索引,顶部写的数字是节点中写的数字。

在第一个示例中,无论您如何排列数字,答案都是$$$1$$$。

在第二个示例中,无论您如何排列数字,答案都是$$$4$$$。

在第三个示例中,实现$$$4$$$的最佳解决方案之一是将$$$4$$$和$$$5$$$安排到节点$$$4$$$和$$$5$$$。

在第四个示例中,最佳解决方案是将 $$$5$$$ 安排到节点 $$$5$$$。