Олимпиадный тренинг

Задача . B. Яблов и дерево


Задача

Темы: Деревья дп поиск в глубину и подобное *2000

У Яблова есть дерево, состоящее из n вершин. Некоторые вершины (по крайней мере одна) покрашены в черный цвет, остальные вершины покрашены в белый цвет.

Рассмотрим множество, состоящее из k (0 ≤ k < n) ребер этого дерева. Если Яблов удалит эти ребра из дерева, то дерево распадется на (k + 1) частей. Каждая часть также будет представлять из себя дерево с покрашенными вершинами.

Теперь Яблову интересно, сколько существует множеств, в результате удаления ребер которых в каждой получившейся части будет ровно одна черная вершина? Выведите это количество по модулю 1000000007 (109 + 7).

Входные данные

В первой строке записано целое число n (2  ≤ n ≤ 105) — количество вершин дерева.

Во второй строке содержится описание дерева: n - 1 целых чисел p0, p1, ..., pn - 2 (0 ≤ pi ≤ i). Где pi означает, что существует ребро, соединяющее вершину (i + 1) и вершину pi дерева. Считайте, что вершины дерева пронумерованы от 0 до n - 1.

В третьей строке записано описание раскраски вершин дерева: n целых чисел x0, x1, ..., xn - 1 (xi равняется либо 0, либо 1). Если xi равняется 1, вершина i покрашена в черный цвет. В противном случае, вершина i покрашена в белый цвет.

Выходные данные

Выведите единственное целое число — количество требуемых множеств по модулю 1000000007 (109 + 7).


Примеры
№Входные данныеВыходные данные
1 3
0 0
0 1 1 
2
2 6
0 1 1 0 4
1 1 0 0 1 0 
1
3 10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1 
27

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет