BOJ)13325 이진 트리

문제: icpc.me/13325

포화 이진트리의 높이 K가 주어 질 때 에지의 가중치를 증가시켜서 루트에서부터 리프까지의 거리를 모두 같게 만드는 문제이다.

아래에서 부터 부모가 같은 두노드의 엣지의 가중치 차이를 바텀업으로 중첩시켜서 증가시켜주면 된다.

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