13325번: Binary Tree

https://www.acmicpc.net/problem/13325

깊은 노드부터 부모로 올라가며 자신 - 단말 노드 거리가 일치하도록 자식과의 거리를 조절한다.
아래 소스의 시간복잡도는 $O(2^k)$

#include<cstdio>
#include<algorithm>
using namespace std;
int k, a[1 << 21], r, i, t;
int main() {
    scanf("%d", &k);
    for (i = 2; i < 1 << k + 1; i++) scanf("%d", a + i);
    while (i -= 2) r += t = max(a[i], a[i + 1]), a[i / 2] += t;
    printf("%d", r + t);
    return 0;
}