eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Декартово дерево

Декартово дерево

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Рассмотрим один специальный тип двоичных деревьев поиска, который часто называют "декартовым деревом". Напомним, что двоичным деревом поиска называется двоичное дерево, в каждой вершине которого записан некоторый ключ (в этой задаче ключ представляет собой целое число), причем для каждой вершины u выполнены следующие условия: все ключи в левом поддереве u меньше чем ключ в вершине u, а все ключи в правом поддереве — больше.

Будем называть двоичное дерево поиска декартовым деревом, если в каждой вершине u помимо основного ключа x_u хранится также вспомогательный ключ y_u, причем для этих ключей выполнено "условие кучи": если v — родитель u, то y_v < y_u.

Будем называть множество пар (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) корректным, если все x_i — различные числа от 1 до n, и то же условие выполнено для y_i. Легко показать, что для любого корректного множества пар существует в точности одно декартово дерево, которое содержит пары из заданного множества в качестве пар ключей.

Рассмотрим двоичное дерево T с n вершинами. Ваша задача — найти количество различных корректных множеств пар, таких что их можно расставить в вершинах T, чтобы превратить его в декартово дерево.

Например, для дерева, приведенного на рисунке, существует три соответствующих корректных множества пар:

{(1, 2), (2, 3), (3, 1), (4, 4)}, {(1, 2), (2, 4), (3, 1), (4, 3)} и {(1, 3), (2, 4), (3, 1), (4, 2)}.

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

Первая строка входного файла содержит n — количество вершин в дереве T (1n200). Следующие n строк описывают его вершины. Каждая вершина описывается двумя числами: номерами левого и правого ребенка. Если один из детей отсутствует, то вместо его номера указан 0. Гарантируется, что описание дерева корректно. Корень дерева имеет номер 1.

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

Выведите одно число — количество различных корректных множеств пар, которые можно расставить в вершинах T, чтобы получилось декартово дерево.

Пример

Входные данные #1
4
2 3
0 4
0 0
0 0
Выходные данные #1
3