Jaś właśnie narysował pełne drzewo binarne i ponumerował jego wierzchołki od góry do dołu i od lewej do prawej kolejnymi liczbami naturalnymi. Tak więc korzeń drzewa otrzymał numer 1, jego lewy syn numer 2, prawy syn numer 3 itd.
Teraz zastanawia się, które z wierzchołków drzewa są korzeniami poddrzew o największej sumie elementów?
Napisz program, który pomoże Jasiowi w znalezieniu odpowiedzi na to pytanie.
Pierwszy wiersz wejścia zawiera liczbę całkowitą n z zakresu
W pierwszym wierszu wyjścia należy wypisać maksymalną możliwą sumę wierzchołków poddrzewa, w wierszu drugim rosnący ciąg numerów tych wierzchołków, które są korzeniami poddrzew o maksymalnej sumie elementów.
Dla danych podanych na wejściu:
3 3 -4 -4 -3 2 5 2
Poprawną odpowiedzią jest wyjście:
5 6
Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5
Opcje zadania:
Biblioteki : iostream iomanip cmath Limit czasu : 0.1 s Limit pamięci : 32 MB Słowa niedozwolone :