Informatica Online Judge

  트리 최댓값 [1232 / 04D0]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 60   Total Tried : 83


The Champion of this Problem (C++) : gs14049 - 0ms / 255byte
My Best Submission (C++) : N/A

[]

Background

complete binary tree가 주어지며 항상 루트 노드에서 출발한다.

예들 들어, 다음과 같은 트리가 주어지고 각 노드 번호는 1에서 n까지 순차적으로 주어지고 각 노드별 가치가 주어진다.



방문한 경로가 #1->#3->#6이라면 얻어지는 총 가치는 #1을 루트로 하는 서브트리내의 노드들의 가치의 합인 17과 #3을 루트로 하는 서브트리내의 노드들의 합인 5와 마지막 #6을 류트로 하는 서브트리내의 노드의 합인 1로 17+5+1=23이 된다.

하지만 #1->#2->#4로 이동하면 17+10+4=31을 얻을 수 있다. 이보다 더 많은 점수를 얻을 수 있는 방법은 없다. 임의의 complete binary tree가 주어질 때, 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에서는 노드의 수 n이 입력된다.
두 번째 줄에는 각 노드의 가치 ai가 입력된다.

[입력값의 정의역]
1 ≤ n ≤ 1,000,000
1 ≤ i ≤ n, 1 ≤ ai ≤ 100

Output

최대 가치를 출력한다.

IO Example

입력 1
7
2 4 1 4 2 1 3
출력 1
31

입력 2
7
1 2 3 4 5 6 7
출력 2
51

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]