Dekart ağacı
Dekart ağacı adlanan xüsusi bir ikili axtarış ağacını nəzərdən keçirək. İkili axtarış ağacı, hər bir zirvəsində müəyyən bir açarın (bu məsələdə açar tam ədəd şəklindədir) yazıldığı ikili ağacdır. Bu ağacda hər bir zirvə u üçün aşağıdakı şərtlər yerinə yetirilməlidir: u zirvəsinin sol alt ağacındakı bütün açarlar u zirvəsindəki açardan kiçik, sağ alt ağacındakı bütün açarlar isə böyük olmalıdır.
Dekart ağacı, ikili axtarış ağacının xüsusi bir növüdür. Burada hər bir zirvə u əsas açar x_u ilə yanaşı, köməkçi açar y_u da saxlayır və bu açarlar üçün "yığın şərti" yerinə yetirilməlidir: əgər v — u-nun əcdadıdırsa, onda y_v < y_u olmalıdır.
Cütlər çoxluğunu (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) doğru adlandırırıq, əgər bütün x_i — 1 ilə n arasında fərqli ədədlərdirsə və bu şərt y_i üçün də yerinə yetirilirsə. İstənilən doğru cütlər çoxluğu üçün dəqiq bir Dekart ağacı mövcuddur ki, bu ağac verilmiş çoxluqdakı cütləri açar cütləri kimi ehtiva edir.
n zirvəli T ikili ağacını nəzərdən keçirək. Sizin vəzifəniz, T ağacının zirvələrində yerləşdirilə bilən və onu Dekart ağacına çevirən müxtəlif doğru cütlər çoxluğunun sayını tapmaqdır.
Məsələn, şəkildə göstərilən ağac üçün üç uyğun doğru cütlər çoxluğu mövcuddur:
{(1, 2), (2, 3), (3, 1), (4, 4)}, {(1, 2), (2, 4), (3, 1), (4, 3)} və {(1, 3), (2, 4), (3, 1), (4, 2)}.
Giriş verilənləri
Giriş faylının ilk sətiri n — T ağacında zirvələrin sayını (1 ≤ n ≤ 200) ehtiva edir. Növbəti n sətir onun zirvələrini təsvir edir. Hər bir zirvə iki ədəd ilə təsvir olunur: sol və sağ uşağın nömrələri. Əgər uşaqlardan biri yoxdursa, onun nömrəsi əvəzinə 0 göstərilir. Ağacın təsvirinin düzgün olduğu təmin edilir. Ağacın kökü 1 nömrəsinə malikdir.
Çıxış verilənləri
Bir ədəd çıxarın — T ağacının zirvələrində yerləşdirilə bilən və Dekart ağacı əldə etmək üçün istifadə edilə bilən müxtəlif doğru cütlər çoxluğunun sayı.