Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ETI07F3 - Filogen

Ostatnia sprawność należy do kategorii specjalistycznych związanych z profilem zastępu i nazywa się "Filogen". Celem sprawdzianu jest weryfikacja umiejętności porównywania historii ewolucji (np. mrówek, którymi interesuje się Jaś) na podstawie wyznaczonych eksperymentalnie drzew filogenetycznych, ukazujących możliwą historię ewolucji (np. od organizmów jednokomórkowych do mrówek). W drzewie binarnym możemy wyróżnić węzły bez potomków (liście), węzły pośrednie (mające jednego rodzica i dokładnie dwóch potomków) oraz korzeń drzewa, który nie ma rodzica, ale ma dwóch potomków. Drzewem filogenetycznym nazywać będziemy dowolne drzewo binarne ze zbiorem liści ponumerowanych od 1 do n (2 <= n <= 10000). Drzewa filogenetyczne będziemy przedstawiać w następujący sposób: z każdym liściem a stowarzyszymy listę jednoelementową La = a; jeżeli dwa liście a oraz b mają wspólnego sąsiada, to stowarzyszymy z nim listę (a b). Niech x i y będą dwoma węzłami w drzewie mającymi wspólnego rodzica oraz załóżmy, że odpowiadają im listy Lx oraz Ly. Wtedy dla ich rodzica tworzymy listę (Lx Ly) (występuje dokładnie jedna spacja pomiędzy listami).

Tor przeszkód
Dla przykładu podanego na rysunku drzewo można opisać listą (((1 2) 5) (3 4)). Z punktu widzenia tworzenia historii ewolucji, nie ma znaczenia, który sąsiad narysowany jest jako lewy, a który jako prawy. Lista ((4 3) ((2 1) 5)) również opisuje to samo drzewo. Zadaniem Jasia jest ustalić, czy dwie podane na wejściu listy opisują to samo drzewo.

Zestawy testowe podzielone są na dwie grupy:
  • zestawy testowe 1-5 [każdy za 2 punkty, limit czasu 1 s]: n <= 1000,
  • zestawy testowe 6-10 [każdy za 2 punkty, limit czasu 5 s]: n <= 10000.

 

Wejście

W pierwszej linii podana została liczba testów t (t <= 100), z których składa się dany zestaw testowy. Następnie każdemu testowi odpowiadają trzy kolejne linie. W pierwszej linii podana została liczba liści n. W drugiej linii podano pierwszą listę, natomiast w trzeciej linii podano drugą listę.

Wyjście

Na wyjściu, dla kolejnych testów w oddzielnych liniach, należy wypisać słowo TAK lub NIE jako odpowiedź na pytanie: czy podane listy opisują to samo drzewo.

Przykład (jednego zestawu testowego)

Wejście:
2
5
(((1 2) 5) (3 4))
((4 3) ((2 1) 5))
3
(1 (2 3))
((1 2) 3)

Wyjście:
TAK
NIE

Dodane przez:mima
Data dodania:2007-02-13
Limit czasu wykonania programu:1s-5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.