In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule. Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Ostatnio Bajtek zobaczył w Bajternecie drzewo bajnarne.
Drzewem bajnarnym nazywamy dowolne ukorzenione drzewo, w którym każdy wierzchołek ma
lub synów.
Wysokością drzewa nazywamy liczbę wierzchołków na najdłuższej ścieżce od korzenia do pewnego z liści; drzewo puste ma wysokość 0.
Na drzewach bajnarnych zdefiniowany jest porządek leksykograficzny.
Drzewo jest leksykograficznie mniejsze od drzewa , gdy:
wysokość drzewa jest mniejsza od wysokości drzewa lub
wysokości drzew i są równe oraz:
lewe poddrzewo jest leksykograficznie mniejsze niż lewe poddrzewo lub
lewe poddrzewo jest równe lewemu poddrzewu i prawe poddrzewo jest leksykograficznie
mniejsze od prawego poddrzewa .
Jeśli dany wierzchołek nie posiada lewego syna, to jego lewe poddrzewo uznajemy za drzewo puste; analogicznie w przypadku braku prawego syna.
Jeśli drzewa i są różne i drzewo nie jest leksykograficznie mniejsze niż drzewo , to
drzewo jest leksykograficznie większe niż drzewo .
Twoje zadanie polega na wczytaniu opisu drzewa i obliczeniu numeru tego drzewa w porządku
leksykograficznym. Drzewo składające się z jednego wierzchołka ma numer .
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba
całkowita () będąca liczbą drzew.
W kolejnych wierszach znajduje się opisów drzew.
W pierwszym wierszu opisu drzewa znajduje się jedna liczba całkowita
() będąca liczbą wierzchołków, z których
składa się drzewo.
Wierzchołki drzewa numerujemy liczbami od do , przy czym wierzchołek jest korzeniem.
Kolejne wierszy opisuje krawędzie drzewa.
-ty z nich zawiera dwie liczby całkowite i () będące numerami
lewego i prawego syna wierzchołka .
W przypadku gdy wierzchołek nie ma lewego syna, , a gdy nie ma
prawego, .
Wyjście
Na standardowe wyjście należy wypisać dokładnie wierszy zawierających
jedną liczbę całkowitą będącą numerem odpowiedniego drzewa w zadanym
porządku modulo .