Standardowym opisem nieskierowanego drzewa o wierzchołkach (ponumerowanych od do ) jest podanie par liczb reprezentujących jego krawędzie. Na wejściu analizowanego zadania dany jest taki właśnie opis, jednakże każda cyfra została zastąpiona znakiem'?'. Na przykład, krawędź między wierzchołkami 90 i 123 byłaby reprezentowana jako "?????". Naszym zadaniem jest odtworzyć jakiekolwiek drzewo pasujące do danego opisu bądź stwierdzić, że takie drzewo nie istnieje.

Niech oznacza największą możliwą liczbę cyfr etykiety wierzchołka (czyli ). Wierzchołki o tej samej liczbie cyfr są, oczywiście, reprezentowane przez ten sam napis, więc w naturalny sposób podzielmy wierzchołki na grup, zgodnie z liczbą cyfr etykiety wierzchołka. Dla każdej pary takich grup znamy żądaną liczbę krawędzi między wierzchołkami tych grup.

Okazuje się, że próba prostego zachłannego odtwarzania naszego drzewa nie rozwiązuje zadania. Również (być może narzucające się) użycie twierdzenia Halla (dla zbiorów grup) też nie jest poprawne. Dobrym pomysłem jest natomiast konstrukcja, w której utrzymujemy cały czas jedną spójną składową i dokładamy do niej nowe krawędzie i wierzchołki.

Spróbujemy w każdej grupie wyróżnić jeden wierzchołek w sposób prowadzący do pewnych dwóch własności. Po pierwsze, chcemy, by krawędzie między wyróżnionymi wierzchołkami łączyły je w jedną spójną składową. Równoważnie, między wyróżnionymi wierzchołkami potrzebujemy krawędzi.

Rozważmy dowolne rozwiązanie (drzewo pasujące do zadanego opisu). Wybierzmy jedną dowolną krawędź między dwoma wierzchołkami z różnych grup i wyróżnijmy te dwa wierzchołki. Dopóki wyróżnionych jest mniej niż wierzchołków, powtarzajmy następujące kroki. Grupę nazwijmy nową, jeśli nie zawiera jeszcze żadnego wyróżnionego wierzchołka. Wierzchołek nazwijmy osiągalnym, jeśli da się do niego dojść z jednego z już wyróżnionych wierzchołków bez przechodzenia przez wierzchołki z nowych grup. Z takich definicji wynika, że istnieje krawędź między osiągalnym wierzchołkiem i wierzchołkiem z nowej grupy. Te dwa wierzchołki oznaczmy jako i Jeśli jest wyróżnione, to po prostu wyróżniamy też W przeciwnym przypadku zastąpmy najpierw krawędź między i krawędzią między i wierzchołkiem wyróżnionym w grupie z (nazwijmy go ). Powstały graf wciąż pasuje do tego samego opisu oraz wciąż jest drzewem, bo po usunięciu krawędzi wierzchołki i są w jednej składowej (bo było osiągalne). Teraz możemy wyróżnić i wciąż spełniony jest żądany warunek, że krawędzie między wyróżnionymi wierzchołkami łączą je w jedną składową.

Po drugie, niech każda krawędź w drzewie dotyka co najmniej jednego wyróżnionego wierzchołka. Jeśli tak nie jest, to spójrzmy na dowolną krawędź między dwoma niewyróżnionymi wierzchołkami z różnych grup. Jako i oznaczmy wyróżnione wierzchołki z grup zawierających odpowiednio i Usuńmy krawędź co dzieli drzewo na dwie składowe. Wiemy, że wyróżnione wierzchołki są ze sobą połączone w jedną składową, zatem i są wciąż w jednej składowej. Po usunięciu krawędzi wierzchołki i muszą być w dwóch różnych składowych, zatem jeden z nich musi być w tej samej składowej co i

Bez straty ogólności powiedzmy, że wierzchołek jest w tej samej składowej co i Zatem wierzchołek jest w innej składowej i możemy go połączyć nową krawędzią z Nowe drzewo wciąż pasuje do zadanego opisu. Podobne rozumowanie można zastosować dla krawędzi między dwoma niewyróżnionymi wierzchołkami z tej samej grupy, co pozostawiamy Czytelnikowi jako proste ćwiczenie. Skoro możemy pozbywać się krawędzi między niewyróżnionymi wierzchołkami, to musi istnieć rozwiązanie, które takich krawędzi nie ma wcale.

Pokazaliśmy, że jeśli istnieje jakiekolwiek rozwiązanie, to istnieje też takie, w którym da się wyróżnić po jednym wierzchołku w każdej z grup w taki sposób, że pewien podgraf drzewa jest drzewem rozpinającym wyróżnionych wierzchołków oraz że nie ma krawędzi między niewyróżnionymi wierzchołkami. Możemy bez straty ogólności powiedzieć, że wyróżniamy wierzchołki o numerach Skoro jest bardzo małe, to po prostu rozważmy kolejno wszystkie drzewa rozpinające o tylu wierzchołkach. W zadaniu tym można to zrobić brutalnie na różne sposoby, natomiast zainteresowanym Czytelnikom polecamy zapoznanie się z kodami Prüfera, które opisują wydajną metodę iteracji po wszystkich etykietowanych drzewach o ustalonej liczbie wierzchołków.

Powiedzmy, że ustaliliśmy krawędzi między wyróżnionymi wierzchołkami. Pozostałe krawędzi nazwijmy zwykłymi. Zwykła krawędź dotyka dokładnie jednego wyróżnionego i jednego niewyróżnionego wierzchołka. Każda taka krawędź musi dotykać innego niewyróżnionego wierzchołka, bo takich wierzchołków jest czyli tyle, ile jest zwykłych krawędzi. Kolejność niewyróżnionych wierzchołków w grupie nie ma znaczenia, bo każdy z nich jest reprezentowany przez ten sam napis na wejściu. Pozostaje zatem dla każdej takiej krawędzi zdecydować, w której z dwóch grup ma ona dotykać wyróżnionego wierzchołka, a w której ma dotykać nowego niewyróżnionego wierzchołka. Pamiętajmy, że w każdej grupie znamy docelową liczbę niewyróżnionych wierzchołków.

Tę ostatnią część zadania możemy rozwiązać za pomocą algorytmu maksymalnego przepływu. Tworzymy wierzchołków reprezentujących grupy. Prowadzimy z nich do ujścia krawędzie o przepustowościach równych liczbom niewyróżnionych wierzchołków w odpowiednich grupach. Tworzymy też wierzchołków do których ze źródła prowadzimy krawędzie o przepustowościach równych liczbom zwykłych krawędzi między grupami i Z prowadzimy krawędzie do i do o nieskończonych przepustowościach. Przepływ o wartości z do należy interpretować jako decyzję, by krawędzi między grupami i dotykało niewyróżnionych wierzchołków w

Rozważyć musimy wszystkie drzew rozpinających na wierzchołkach i dla każdego znaleźć przepływ w grafie o wierzchołkach i krawędziach. Przykładowa złożoność takiego programu to gdzie obecność składnika wynika z konieczności właściwego odtworzenia i wypisania drzewa o wierzchołkach.

Zainteresowanym proponujemy zastanowić się, czy możemy zamiast metody maksymalnego przepływu użyć twierdzenia Halla.