深度优先搜索 - 塔子哥的完整二叉树

一、问题分析

• 给定一棵 完整二叉树，每个节点要么 没有子节点（叶子），要么 有两个子节点（非叶子）。
• 叶子节点的权值为 1。
• 非叶子节点的权值 由其 左右子节点的权值 计算：
  • c[i] = 0 → 加法：权值 = 左子权值 + 右子权值
  • c[i] = 1 → 乘法：权值 = 左子权值 × 右子权值
• 求 根节点的权值，结果取 模 $10^9 + 7$。

本题为2023年9月8日百度机考原题

百度机考的介绍点击这里

题目描述

塔子哥有一棵节点数为 $n$ 的完整二叉树，对于一个完整二叉树的定义是：要么每个节点有两个子节点，要么每个节点没有子节点。

• 没有子节点的节点，其权值为 $1$ 。
• 有两个子节点的节点，其权值为两个儿子节点的权值的运算结果。

每个节点有两种运算，要么为加法，要么为乘法。如下给出一个长度为 $n$ 的数组 $c$ 。

$c_i=0$ 表示节点 $i$ 的运算是加法，$c_i=1$ 表示节点 $i$ 的运算是乘法。

现在，塔子哥问你这个完整二叉树的根节点的权值是多少。

输入描述

第一行，一个正整数 $n(1\leq n\leq 10^5)$ 表示完整二叉树中的节点个数。

第二行，$n-1$ 个正整数 $p[2,3,...,n]$，$p[i](1\leq p[i]\leq n)$ 表示第 $i$ 个节点的父节点，$1$ 号节点是根节点。

第三行，$n$ 个整数 $c[1,2,...,n]$ ，含义如题面描述所示

数据保证形成满足题目描述的二叉完整树。

输出描述

一个整数，表示根节点的值，答案对 $10^9+7$ 取模。

样例

输入

3
1 1
1 1 1

输出

1

说明

$2$ 号节点和 $3$ 号节点权值均为 $1$ ，$1$ 号节点是乘法运算，故 $1$ 号节点的权值为 $1$ 。