Рассмотрим один специальный тип двоичных деревьев поиска, который часто называют "декартовым деревом". Напомним, что двоичным деревом поиска называется двоичное дерево, в каждой вершине которого записан некоторый ключ (в этой задаче ключ представляет собой целое число), причем для каждой вершины u выполнены следующие условия: все ключи в левом поддереве u меньше чем ключ в вершине u , а все ключи в правом поддереве - больше. Будем называть двоичное дерево поиска декартовым деревом, если в каждой вершине u помимо основного ключа х _u хранится также вспомогательный ключ y _u , причем для этих ключей выполнено "условие кучи": если v - родитель u , то y _v < y _u . Будем называть множество пар ( x ₁ , y ₁ ), ( х ₂ , y ₂ ), ... ( х _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)}.