21488번 - Красно-черные деревья 다국어

Широкое распространение в стандартных библиотеках многих языков программирования получила реализация сбалансированных деревьев на основе так называемых красно-черных деревьев. В данной задаче вам предлагается посчитать количество красно-черных деревьев заданной формы.

Напомним, что двоичным деревом называется набор вершин, организованных в виде дерева. Каждая вершина имеет не более двух детей, один из которых называется левым, а другой --- правым. Как левый, так и правый ребенок, а также оба могут отсутствовать. 

Если вершина $Y$ --- ребенок вершины $X$, то говорят, что вершина $X$ является родителем вершины $Y$. У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.

Соединим каждую вершину кроме корня с ее родителем. Заметим, что для каждой вершины существует ровно один путь, ведущий в нее от корня.

Двоичное дерево называется красно-черным, если каждая его вершина раскрашена в красный либо в черный цвет, причем выполняются следующие условия:

1. если вершина красная, то ее родитель --- черный;
2. количество черных вершин на пути от корня до любой вершины, у которой отсутствует хотя бы один ребенок, одно и то же.

Примеры двоичного дерева, вершины которого раскрашены в два цвета, приведены на следующем рисунке. 

(а)	(б)	(в)

Если считать закрашенные вершины черными, а незакрашенные --- красными, то дерево на рисунке (а) является красно-черным деревом, а деревья на рисунках (б) и (в) --- нет. Для дерева на рисунке (б) нарушается первое свойство --- у красной вершины 5 родитель 2 также красный, а в дереве на рисунке (в) нарушается второе свойство --- на пути от корня до вершины 1 одна черная вершина, а, например, на пути от корня до вершины 3 --- две.

Для заданного двоичного дерева подсчитайте число способов раскрасить его вершины в черный и красный цвет так, чтобы оно стало красно-черным деревом.

Первая строка входного файла содержит число $n$ --- количество вершин в дереве ($1 \le n \le 1000$).

Пусть вершины дерева пронумерованы числами от $1$ до $n$. Следующие $n$ строк содержат по два числа --- для каждой вершины заданы номера ее левого и правого ребенка. Если один из детей отсутствует, то вместо его номера записан ноль. Гарантируется, что входные данные корректны, то есть набор чисел во входном файле действительно задает двоичное дерево.

Выведите в выходной файл одно число --- количество способов раскрасить вершины заданного во входном файле двоичного дерева в красный и черный цвета так, чтобы оно стало красно-черным деревом.

Все допустимые способы раскрасить вершины дерева из первого примера приведены на следующем рисунке.