黑白树分割 - 代码源竞赛平台

题目描述

蜗蜗有一棵包含 $n$ 个节点的树，节点编号为 $0$ 到 $n-1$。每个节点都被染成黑色或白色，树上至少有一个黑色节点。

蜗蜗可以删除若干条边，使剩下的每个连通块都恰好包含一个黑色节点，也可以一条边都不删除。只要删除的边集合不同，就视为不同的方案。

请你求出满足条件的方案数量，答案对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $n$，表示节点数量。

第二行包含 $n-1$ 个整数 $p_0,p_1,\ldots,p_{n-2}$，其中 $p_i$ 表示节点 $i+1$ 与节点 $p_i$ 之间有一条边。

第三行包含 $n$ 个整数 $x_0,x_1,\ldots,x_{n-1}$。当 $x_i=1$ 时，节点 $i$ 为黑色；当 $x_i=0$ 时，节点 $i$ 为白色。

输出格式

输出一行一个整数，表示满足条件的删边方案数量对 $10^9+7$ 取模的结果。

样例

4
0 1 2
1 0 0 1

3

样例解释

四个节点依次连接成一条链，节点 $0$ 和节点 $3$ 为黑色，中间两个节点为白色。

删除三条边中的任意一条，都可以得到两个各含一个黑色节点的连通块，因此共有 $3$ 种方案。

数据范围

对于 100% 的数据，保证 $2\le n\le 10^5$，$0\le p_i\le i$（$0\le i\le n-2$），$x_i\in\{0,1\}$，且至少有一个 $x_i=1$。