Toto je starší verze dokumentu!

První řádek vstupu je N = počet uzlů. Doporučuji si po přečtení tohoto čísla inicializovat pole a přidat nové uzly do něj.

Dalších N-1 řádků reprezentuje jednotlivé hrany, v neurčeném pořadí. V každém řádku si propojte dané objekty tak, aby se vám snadno procházely při rekurzivním DFS.

Pro zahájení algoritmu potřebujeme zjistit kořen. To se pravděpodobně nedá udělat o moc lépe, než mít každý uzel na začátku nastavený, že je kořen, a při čtení hran tuto informaci vypínat - pokud nějaký uzel nastavuju do left/right ukazatele jeho rodiče, už to nemůže být kořen. Po přečtení všech hran v poli uzlů zbyde jediný uzel, který tuto informaci má nastavenou na true.

Od tohoto uzlu (kořene) spustíme DFS procházení. Úkolem je najít vzájemně nepodobné podstromy ve stromu a vypsat jejich počet. Definice podobnosti je v zadání, zkráceně:

Podstrom je vždy reprezentován jeho kořenem a jeho potomky. Každý uzel ve stromě je tedy reprezentant takového podstromu. Cílem je najít a spočítat všechny vzájemně nepodobné podstromy. V momentě, kdy porovnávám dva podstromy, musí souhlasit váha na levé hraně a jejich levé podstromy a zároveň váha na pravé hraně a jejich pravé podstromy, případně mohu hrany prohodit (pokud souhlasí levá a pravá hrana, musí souhlasit levý a pravý podstrom).

Jádrem řešení je tedy vygenerovat si pro každý uzel takový identifikátor, který bude odlišný pro nepodobné stromy a stejný pro podobné stromy. Já se vydal cestou reprezentace stringem. Pro každý uzel jsem před svislítko dal certifikát podstromu, do kterého vede větší hrana a za svislítko certifikát podstromu, do kterého vede menší hrana.

Neexistující hrany mají cerifikát inf, listy tedy inf|inf. V example 4 mají uzly 3, 4, 5 tento certifikát:

8(inf|inf)|5(7(inf|inf)|inf)

Vedle si držím seznam dosavadních výsledků, při uzavírání uzlu v DFS si vygeneruji tento certifikát a porovnám ho se všemi dosavadními výsledky. Pokud se se žádným neshoduje, do seznamu ho přidám, jinak ho zahodím.

Na konci vypíšu počet těchto výsledků + 1, protože se mezi ně počítá i prázdný strom (na který ale při procházení v DFS samozřejmě nenarazíte).

Toto řešení získalo 10/12 a pravděpodobně by se dalo urychlit jinou reprezentací a porovnáváním certifikátů.