提示:我们在题目描述的最后一段提供了一份简要的、形式化描述的题面。
在遥远的未来,物理学家终于发现了时间和因果的自然规律。即使在一个人出生前,我们也可以通过理论分析知晓他或她人生的一些信息,换言之,物理学允许我们从一定程度上“预言”一个人的“命运”。
简单来说,一个人的命运是一棵由时间点构成的有根树
一个人的一生是从出生(即根结点)到死亡(即某一个叶子结点)的一条不经过重复结点的路径,这条路径上任何一个包含至少一条边的子路径都是这个人的一段人生经历,而他或她以所有可能的方式度过一生,从而拥有的所有人生经历,都被称为潜在的人生经历。换言之,所有潜在的人生经历就是所有
物理理论不仅允许我们观测代表命运的树,还能让我们分析一些潜在的人生经历是否是“重要”的。一个人所作出的每一个选择——即树上的每一条边 —— 都可能是重要或不重要的。一段潜在的人生经历被称为重要的,当且仅当其对应的路径上存在一条边是重要的。我们可以观测到一些潜在的人生经历是重要的:换言之,我们可以观测得到 一个集合
树
形式化的:给定一棵树
输入格式
第一行包含一个正整数
接下来
接下来一行包含一个非负整数
接下来
输入数据规模和限制参见本题末尾的表格。
输出格式
输出仅一行一个整数,表示方案数对
样例一
input
5 1 2 2 3 3 4 3 5 2 1 3 2 5
output
10
explanation
共有 16 种方案,其中不满足题意的方案有以下 6 种:
确定为不重要, 确定为重要:集合 中没有限制被满足。 确定为不重要:集合 中没有限制被满足。 确定为不重要, 确定为重要:集合 中 没被满足。 确定为不重要, 确定为重要:集合 中 没被满足。 确定为不重要, 确定为重要:集合 中 没被满足。 确定为不重要, 确定为重要:集合 中 没被满足。- 其他方案下,集合
中的限制都被满足了。
样例二
input
15 2 1 3 1 4 3 5 2 6 3 7 6 8 4 9 5 10 7 11 5 12 10 13 3 14 9 15 8 6 3 12 5 11 2 5 3 13 8 15 1 13
output
960
样例三
见样例数据下载。
样例四
见样例数据下载。
数据范围
测试点编号 | |||
---|---|---|---|
否 | |||
是 | |||
否 | |||
全部数据满足:
完全二叉树:在本题中,每个非叶结点都有左右子结点,且所有叶子结点深度相同的树称为满二叉树;将满二叉树中的结点按照从上到下、从左向右的顺序编号,编号最小的若干个结点形成的树称为完全二叉树。
时间限制:
空间限制: