Задачи
Декартово дерево
Декартово дерево
Рассмотрим один специальный тип двоичных деревьев поиска, который часто называют "декартовым деревом". Напомним, что двоичным деревом поиска называется двоичное дерево, в каждой вершине которого записан некоторый ключ (в этой задаче ключ представляет собой целое число), причем для каждой вершины \textbf{u} выполнены следующие условия: все ключи в левом поддереве \textbf{u} меньше чем ключ в вершине \textbf{u}, а все ключи в правом поддереве --- больше.
Будем называть двоичное дерево поиска декартовым деревом, если в каждой вершине \textbf{u} помимо основного ключа \textbf{x_u} хранится также вспомогательный ключ \textbf{y_u}, причем для этих ключей выполнено "условие кучи": если \textbf{v} --- родитель \textbf{u}, то \textbf{y_v} < \textbf{y_u}.
Будем называть множество пар (\textbf{x_1}, \textbf{y_1}), (\textbf{x_2}, \textbf{y_2}), ..., (\textbf{x_n}, \textbf{y_n}) \textit{корректным}, если все \textbf{x_i} --- различные числа от \textbf{1} до \textbf{n}, и то же условие выполнено для \textbf{y_i}. Легко показать, что для любого корректного множества пар существует в точности одно декартово дерево, которое содержит пары из заданного множества в качестве пар ключей.
Рассмотрим двоичное дерево \textbf{T} с \textbf{n} вершинами. Ваша задача --- найти количество различных корректных множеств пар, таких что их можно расставить в вершинах \textbf{T}, чтобы превратить его в декартово дерево.
Например, для дерева, приведенного на рисунке, существует три соответствующих корректных множества пар:
\textbf{\{(1},\textbf{ 2)},\textbf{ (2},\textbf{ 3)},\textbf{ (3},\textbf{ 1)},\textbf{ (4},\textbf{ 4)\}}, \textbf{\{(1},\textbf{ 2)},\textbf{ (2},\textbf{ 4)},\textbf{ (3},\textbf{ 1)},\textbf{ (4},\textbf{ 3)\}} и \textbf{\{(1},\textbf{ 3)},\textbf{ (2},\textbf{ 4)},\textbf{ (3},\textbf{ 1)},\textbf{ (4},\textbf{ 2)\}}.
\includegraphics{https://static.e-olymp.com/content/00/00abd9c2467bf626ac2c64a19ffd566b56c6887b.jpg}
\InputFile
Первая строка входного файла содержит \textbf{n} --- количество вершин в дереве \textbf{T} (\textbf{1} ≤ \textbf{n} ≤ \textbf{200}). Следующие \textbf{n} строк описывают его вершины. Каждая вершина описывается двумя числами: номерами левого и правого ребенка. Если один из детей отсутствует, то вместо его номера указан \textbf{0}. Гарантируется, что описание дерева корректно. Корень дерева имеет номер \textbf{1}.
\OutputFile
Выведите одно число --- количество различных корректных множеств пар, которые можно расставить в вершинах \textbf{T}, чтобы получилось декартово дерево.
Входные данные #1
4 2 3 0 4 0 0 0 0
Выходные данные #1
3