Задача №112548. Декартово дерево
Рассмотрим один специальный тип двоичных деревьев поиска, который часто называют "декартовым деревом". Напомним, что двоичным деревом поиска называется двоичное дерево, в каждой вершине которого записан некоторый ключ (в этой задаче ключ представляет собой целое число), причем для каждой вершины
u
выполнены следующие условия: все ключи в левом поддереве
u
меньше чем ключ в вершине
u
, а все ключи в правом поддереве - больше. Будем называть двоичное дерево поиска декартовым деревом, если в каждой вершине
u
помимо основного ключа
х
u
хранится также вспомогательный ключ
y
u
, причем для этих ключей выполнено "условие кучи": если
v
- родитель
u
, то
y
v
<
y
u
. Будем называть множество пар
(
x
1
,
y
1
), (
х
2
,
y
2
), ... (
х
n
,
у
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 (1 ≤ n ≤ 200) следующие n строк описывают его вершины. Каждая вершина описывается двумя числами: номерами левого и правого ребёнка. Если один из детей отсутствует, то вместо его номера указан 0. Гарантируется, что описание дерева корректно. Корень дерева имеет номер 1.
Выведите одно число – количество различных корректны множеств пар, которые можно расставить в вершинах T , чтобы получилось декартово дерево.
4 2 3 0 4 0 0 0 0
3