İzomorf suffiks ağacları
Bu tapşırıqda, verilmiş kök ağacına T izomorf olan '0' və '1' simvollarından ibarət müxtəlif sətirlərin sayını tapmaq lazımdır.
İki kök ağacı izomorf adlanır, əgər hər ikisi eyni sayda n zirvədən ibarətdirsə və hər birinin zirvələrini 1-dən n-ə qədər müxtəlif tam ədədlərlə nömrələmək mümkündürsə ki:
hər iki ağacın kökləri eyni nömrələrə malikdir;
birinci ağacda a və b nömrəli zirvələr arasında kənar varsa, yalnız o halda ikinci ağacda da a və b nömrəli zirvələr arasında kənar var.
Bu tapşırıqda sətir s üçün sufix ağacı aşağıdakı şərtlərə cavab verən kök ağacıdır:
Ağacın hər bir kənarına '0' və '1' simvollarından ibarət boş olmayan bir sətir uyğun gəlir.
Sətirin s+''} hər bir sufixinə, sufix "\textbf{" istisna olmaqla, yalnız bir yarpaq (yəni köklə üst-üstə düşməyən dərəcəsi 1 olan zirvə) uyğun gəlir ki, kökdən bu yarpağa qədər olan yolda kənarların sətirlərinin konkatenasiyası həmin sufixə bərabərdir.
Ağacın nə yarpaq, nə də kök olmayan hər hansı bir zirvəsinin dərəcəsi ikidən çoxdur.
Ağac, 1-3 xüsusiyyətlərinə cavab verən bütün ağaclar arasında kənarlarda yazılmış sətirlərin ümumi uzunluğu mümkün olan ən minimal olanıdır.
Məsələn, "1100" sətiri üçün sufix ağacı aşağıdakı kimidir:
Xatırladaq ki, sizin tapşırığınız verilmiş kök ağacına T görə, sufix ağacları T-yə izomorf olan '0' və '1' simvollarından ibarət müxtəlif sətirlərin sayını müəyyən etməkdir.
Giriş verilənləri
Birinci sətir ağacın zirvələrinin sayı olan tam ədəd n (2 ≤ n ≤ 25) ehtiva edir. Ağacın zirvələri 1-dən n-ə qədər tam ədədlərlə nömrələnmişdir. Ağacın kökü 1 nömrəli zirvədir. Növbəti n-1 sətirdə ağacın kənarları təsvir edilir. Bu sətirlərin hər biri ağacın növbəti kənarını birləşdirən zirvələrin nömrələri olan iki tam ədəd x_i və y_i (1 ≤ x_i, y_{i }≤ n, x_{i }≠ y_i) ehtiva edir.
Çıxış verilənləri
Birinci sətir verilmiş məlumatlarda təsvir edilən ağaca izomorf olan sufix ağacları olan sətirlərin sayını göstərən tam ədəd c ehtiva etməlidir (ən azı bir belə sətirin mövcudluğu təmin edilir). Növbəti c sətirdə bütün axtarılan sətirlər verilməlidir. Bu sətirləri leksikoqrafik ardıcıllıqla çıxarın.