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 -1 -3 2 10 3 7
Poprawną odpowiedzią jest wyjście:
15 1
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 :