2-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"D" Красно-черное дерево
Ограничение по времени 3 секунды
Ограничение по памяти 256 мегабайт

Знали ли вы, что в большинстве стандартных библиотек структура данных «множество» реализовано с использованием красно-черного дерева? В этой задаче вам необходимо найти количество способов покрасить заданное двоичное дерево так, чтобы оно стало красно-черным. Ответ необходимо вывести по модулю 109 + 7.

Рассмотрим двоичное дерево. Если у вершины меньше двух детей, добавим на место недостающих детей фиктивные вершины. Дерево называется красно-черным, если выполняются следующие свойства:

  1. Каждая вершина покрашена в один из двух цветов: красный или черный.
  2. Корень дерева и все добавленные фиктивные вершины покрашены в черный цвет.
  3. Родитель вершины, покрашенной в красный цвет, покрашен в черный цвет.
  4. Все пути от корня до добавленных фиктивных листьев содержат одинаковое количество черных вершин.

Обратите внимание, что родитель вершины, покрашенной в черный цвет, может быть покрашен в черный цвет.

Две раскраски дерева называются различными, если существует вершина, которая покрашена в разные цвета в этих раскрасках.

На рисунке приведены два способа покраски дерева из второго теста.

Формат входных данных

В первой строке содержится одно целое число n — количество вершин в дереве (1 ≤ n ≤ 500 000).

Следующие n строк описывают дерево. В i-й строке содержатся два целых числа li и ri — индексы вершин, являющихся левым и правым детьми i-й, либо 0, если соответствующий ребенок отсутствует (li = 0 или i < li ≤ n; ri = 0 или i < ri ≤ n). Корень дерева имеет номер 1. Гарантируется, что во вводе описано корректное дерево.

Формат выходных данных

Выведите одно целое число — число способов покрасить заданное дерево, чтобы оно стало красно-черным. Ответ необходимо вывести по модулю 109 + 7.

Примеры
Входные данные
3
2 3
0 0
0 0
Выходные данные
2
Входные данные
6
2 4
3 0
0 0
5 6
0 0
0 0
Выходные данные
2
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.