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:
4 10 3 5 5 2 4 10 0 2 -6 -3 1 -3 -9 -1
Poprawną odpowiedzią jest wyjście:
20 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 :