백준(BOJ) 13325 이진트리 *

# 트리 #자료 구조

1. 루트에서 리프까지 거리 중 최대 거리를 찾는다.

2. 리프에서 루트로 올라오면서 각 노드들을 update 시켜준다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 1005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n,mx=-1,arr[2100000];

void getmax(int node,int h,int sum)
// 루프와 리프들의 거리 중 최대값을 구한다.
{
    if(n==h)
    {
        sum+=arr[node];
        mx=mx<sum?sum:mx;
        return;
    }
    getmax(node*2,h+1,sum+arr[node]);
    getmax(node*2+1,h+1,sum+arr[node]);
}

int update(int node,int h,int sum)
// 트리의 밑에서 부터 루트로 올라오면서 값들을 업데이트 시켜준다.
{
    if(n==h)
        return mx-(sum+arr[node]);
    // 최대 높이에 도달하였을때
    int a=update(node*2,h+1,sum+arr[node]);
    int b=update(node*2+1,h+1,sum+arr[node]);
    // 먼저 가장 밑의 노드로 이동한다.
    int mi=min(a,b);
    // 양 노드에 더해야 하는 최소 값은 상위 노드로 리턴해준다. (양 노드에 1,2를 더해야 한다면 1은 리턴)
    arr[node*2]+=(a-mi);
    arr[node*2+1]+=(b-mi);
    // 양 노드에 더해야 하는 최소 값을 넘는 값은 각 노드에 더 해준다. (양 노드에 0,1을 더해 준다)
    return mi;
}

int main()
{
    scanf("%d",&n);
    for(int i=2;i<pow(2,n+1);i++)
        scanf("%d",&arr[i]);
    getmax(1,0,mx);
    update(1,0,0);
    ll ans=0;
    for(int i=1;i<pow(2,n+1);i++)
        ans+=(ll)arr[i];
    printf("%lld",ans);
    return 0;
}