18251번 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 하나 이상의 노드를 포함해야 하고 직사각형은 비뚤어지면 안 된다.

문제에서 생략된 정의는 다음과 같다. 이해가 안 되면 읽어보자.

1. 직사각형은 축에 평행하며, 변이 노드에 걸치면 안 된다.
2. 모든 노드 u에 대해, u의 왼쪽 서브 트리에 속하는 모든 노드의 x좌표는, u의 x좌표보다 작다.
3. 모든 노드 u에 대해, u의 오른쪽 서브 트리에 속하는 모든 노드의 x좌표는, u의 x좌표보다 크다.
4. 자식 노드의 y좌표는 부모 노드의 y좌표보다 작다.
5. 트리에서의 깊이가 같은 노드의 y좌표는 모두 같다.

첫째 줄에 노드 개수 N이 주어진다. (1 ≤ N ≤ 262,143, N은 2^k-1 꼴의 자연수)

둘째 줄에 노드의 가중치 W_i가 노드 번호 순서대로 주어진다. (-10⁹ ≤ W_i ≤ 10⁹)

루트 노드의 번호는 1이고, i번 노드의 좌우 자식 노드의 번호는 각각 2×i, 2×i+1이다.

욱제가 얻을 수 있는 가중치의 최대 합을 출력한다.