홍준이와 트리 2

시간 제한2초메모리 제한512 MB

요약

트리에서 간선을 잘라 모든 조각이 검은 정점을 정확히 하나씩 포함하도록 만드는 방법의 수를 세어 1e9+7로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 트리, DFS, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

0번부터 $N-1$ 번까지 번호가 붙은 $N$ 개의 정점으로 이루어진 트리가 주어진다.

각 정점은 흰색 또는 검은색으로 칠해져 있고, 두 색 모두 최소 한 개의 정점에 칠해져 있음이 보장된다.

이때 트리에서 간선 $k$ 개( $0 \le k < N$ )를 골라 없앨 수 있다. 그러면 정점 집합이 $k+1$ 개로 나뉜다. 나뉜 집합이 모두 검은색 정점을 정확히 하나씩만 포함하도록 트리를 분할하는 경우의 수를 구하시오. 값이 매우 커질 수 있으므로 $10^9+7$ 로 나눈 나머지를 출력한다.

입력

첫째 줄에 정점의 개수 $N$ ( $1 \le N \le 100000$ )이 주어진다.

둘째 줄에 $N-1$ 개의 정수 $p_0, p_1, \dots, p_{N-2}$ ( $0 \le p_i \le i$ )가 주어진다. 정점 $p_k$ 와 정점 $k+1$ 을 잇는 간선이 있다는 뜻이다.

셋째 줄에 각 정점의 색을 나타내는 $N$ 개의 정수 $x_0, x_1, \dots, x_{N-1}$ 이 주어진다. $x_i$ 가 0이면 $i$ 번 정점이 흰색, 1이면 검은색이다.

출력

조건을 만족하는 분할의 경우의 수를 $10^9+7$ 로 나눈 나머지를 한 줄에 출력한다.

예제7

예제 1
입력
```
3
0 0 
0 1 1
```
예상 출력
```
2
```
예제 2
입력
```
2
0
0 1
```
예상 출력
```
1
```
예제 3
입력
```
3
0 0
1 1 0
```
예상 출력
```
1
```
예제 4
입력
```
6
0 0 0 0 0
1 0 0 0 0 0
```
예상 출력
```
1
```
예제 5
입력
```
6
0 0 0 0 0
0 1 1 1 1 1
```
예상 출력
```
5
```
예제 6
입력
```
8
0 1 2 3 4 5 6
0 1 0 1 0 1 0 1
```
예상 출력
```
8
```
예제 7
입력
```
7
0 1 0 3 0 5
1 0 1 0 1 0 1
```
예상 출력
```
8
```