← 返回题目列表

Codeforces · 1034/C

C. 区域分离

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

秋之国共有$$$n$$$个城市,编号从$$$1$$$到$$$n$$$。人们可以使用 $$$n-1$$$ 双向道路在任意两个城市之间旅行。

今年,政府决定分离王国。将会有不同级别的区域。整个王国将是$$$1$$$级别的区域。 $$$i$$$-th 级别的每个区域应分为多个(至少两个)$$$i+1$$$-th 级别区域,除非 $$$i$$$-th 级别是最后一个级别。每个城市应该属于每个级别的一个区域,并且对于同一区域中的任意两个城市,应该可以仅通过同一区域中的城市在它们之间旅行。

根据研究,对于每个城市$$$i$$$,都有一个值$$$a_i$$$,描述了这个城市的重要性。同一级别的所有区域的城市重要性总和应相等。

你的任务是找出有多少个计划来确定满足所有条件的区域的分离。当且仅当两个规划的级别数不同,或者一个规划中一个级别的同一区域存在两个城市,而另一个规划中该级别的不同区域存在两个城市时,两个规划才被视为不同。由于答案可能非常大,因此输出它对 $$$10^9+7$$$ 取模。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — 城市的数量。

第二行包含 $$$n$$$ 整数,其中第 $$$i$$$ 是 $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — 每个城市的值。

第三行包含$$$n-1$$$整数,$$$p_1, p_2, \ldots, p_{n-1}$$$; $$$p_i$$$ ($$$p_i \leq i$$$) 描述了城市 $$$p_i$$$ 和 $$$i+1$$$ 之间的道路。

输出

打印一个整数 — 不同计划的数量以 $$$10^9+7$$$ 为模。

示例

输入 #1

4
1 1 1 1
1 2 3

输出 #1

4

输入 #2

4
1 1 1 1
1 2 2

输出 #2

2

输入 #3

4
1 2 1 2
1 1 3

输出 #3

3

注意

对于第一个示例,有 $$$4$$$ 不同的计划:

计划$$$1$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$。

计划$$$2$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1,2\}$$$,$$$\{3,4\}$$$。

计划$$$3$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1\}$$$、$$$\{2\}$$$、$$$\{3\}$$$、$$$\{4\}$$$。

计划 $$$4$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1,2\}$$$,$$$\{3,4\}$$$,级别-$$$3$$$: $$$\{1\}$$$、$$$\{2\}$$$、$$$\{3\}$$$、$$$\{4\}$$$。

对于第二个示例,有 $$$2$$$ 不同的计划:

计划$$$1$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$。

计划$$$2$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1\}$$$、$$$\{2\}$$$、$$$\{3\}$$$、$$$\{4\}$$$。

对于第三个示例,有 $$$3$$$ 不同的计划:

计划$$$1$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$。

计划$$$2$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1,2\}$$$,$$$\{3,4\}$$$。

计划$$$3$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1,3\}$$$,$$$\{2\}$$$,$$$\{4\}$$$。